Without seeing the actual image it's difficult to say, but I suspect it has to do with the fact that the background in your image is only approximately white (it looks white to your eye, but technically is not white). So when you select real white brush, you do see that contrast.
I suggest you try using Clone Stamp tool. The way to do it is to select background source near the element you want to remove (Ctrl+Click to set anchor), and then just draw over the element. Paint.NET will simply "clone" the pixels from the source onto the element you are removing, thus making the background look the same.
If the background is really just one color, you can just color-pick it and use that as a brush.