Yes it's possible, although it definitely requires skill and patience.
You can see the work that I did on a picture from Seattle. The original is here, http://www.eecs.wsu.edu/paint.net/scree ... CN1262.jpg , and you can note the power lines crossing in front of the Space Needle that obscure things really bad.
After I spent several hours with the Clone Stamp and various other Paint.NET tools, I ended up with this: http://www.deviantart.com/deviation/27687013/ . Note that the foreground power lines are completely gone. I also did some contrast and saturation adjustments that really turned out well.
Unfortunately I can't provide much in the way of a tutorial for several reasons. It's not necessarily simple to perform, and the work required varies and depends heavily on the nature and quality of the source image. The other reason is that I'm tired and just don't have enough time to go into this except to say that yes it is possible with Paint.NET.