Reinigen ist auf jeden fall das A und O.
Danach würd ich mal versuchen das Bild in einer wesentlich höeren Auflösung zu scanen, und es dann in PS wieder auf die richtige größe runterrechen.
Wenn man dann vor dem "Verkleinern" den Ein oder anderen Filter anwendet könnte es besser werden.
Das mit der höheren Auflösung verhindert kleine Kästchen/Rautenbildung die beim Scannen von Bildern, aber vorallem Zeitschriften entstehen (Druckerzeugnisse), Diese sollte bei fotos aber eher weniger auftauchen.
Ist nur ein versuch...
viel glück dabei!