Haha! Of course! That works great! I find that frosted glass :FrostedGlass: with settings 4,0,1 mimics the effect almost perfectly for most gradients.
So there! Don't come to hasty conclusions. In order to fully implement this, one would merely need to make the gradient tool apply the frosted glass effect afterwards with the maximum scatter radius as a function of the difference between the two gradient colors and its total length.
I see no reason why this should not be used in replacement of the current gradient tool.
Um.... what? I've done the effect myself and it does solve the problem. You see, the issue is that Paint.NET gradients make rectangles of color transitioning between two colors. If you're going from FFFFFF to FDFFFF then there's only one intermediate color and hence there will be only three rectangles - which can be really bad-looking. Frosted glass fixes this because it blurs the edges between the rectangles. Gaussian blurring wouldn't work because the adjacent rectangles are already as close together as possible without being the same color - so frosted glass is the only way to go. Also, if you make the maximum scatter radius a function of the size of the rectangles and the overall gradient, the effect would work fine for any size of gradient.
Bam. You can see pretty clearly the gradient lines on the left even outside of the selection. But on the right...