hi jaso,
there are basically two methods for removing these sorts of problems, the bulk method like Neat Image, Polaroid D&S, and
PSP's digital camera noise removal, or, the manual method, like clone, heal and so on. you've already named the drawbacks on both. the bulk tends to smudge and remove parts you dont want removed and the manual takes a longer time.
i find in images like this that a combination of both works pretty well. you can shorten the work time with bulk, but set it to a lighter setting to not remove as much, and then do some manual. also, instead of 'darkness', try 'luminance' or 'soft light' for the blend mode.
you might also try several layers of the bulk type and blend modes. take your original background layer and dupe it several times. on each layer use a different degree of the bulk work then try blending the different layers and varying the opacities.
myself, i enjoy cloning. i find it relaxing and have a lot more control over the finished product. i can also clone fairly fast any more. i also use the push brush as a clone tool at times. but, i also use the bulk techniques for speed when desired.
your image doesnt appear that difficult, but then i'm not looking at it zoomed in right now.
Craig
Craig