Hello Ran,
I thought I would give this a go, sin ce I've been reading up on fixing old photos myself. Here is what I came up with (as best as possible working with a JPEG):
A great book that would help with projects like this is The Photoshop 7 WOW Book, by Jack Davis. This book has tons of awesome tutorials on fixing, retouching, and working with photos. Not to mention working with styles, brushes, and more.
One of the best tricks I learned from Davis' book was a variation of the following (for getting rid of spots on photos):
1) Duplicate the layer on which you are working.
2) To the duplicate layer apply Filter > Noise > Dust & Scratches, and adjust the settings so that the spots are no longer visible (in this case it was Radius:6, Threshold:0).
3) Add a mask to the duplicate layer, it's the second button from the left on the bottom of the layer palette.
4) Click on the mask you have just made and go to Image > Adjustments > Invert. You now see your original image, the mask is black (fully transparent).
5) Take the brush tool at a convenient setting and paint with white over the damaged areas. Watch the spots disappear as you paint back the layer above.
Hope this helps.
- dc