Ich halte von niedrigen Scan-DPIs nichts (eher ne psychologische Sache, Scan das Bild extra schlecht, damit man nicht merkt wie gut es eigentlich wäre) und vom Runtersetzen auf 256 Farben "vor" dem Verkleinern halte ich auch nichts, da dann nur noch Pixelverkleinerungen aber keine bicubischen oder bilinearen mehr funktionieren.

@Knopey: Meinst du bezüglich der Übergänge die Übergänge zum Hintergrund? Den solltest du vorher erstmal grau bis schwarz einfärben (ich nehme selbst in solchen Dingen immer dunkelgrau). Dann interpoliert er die Ränder in richtung dieses Graus und nicht in Richtung Magenta, wie in deinem Bild. Folglich sollte das Bild dann auch einen (unauffälligen) neutral-dunklen Rand haben und nichts pinkes mehr. Den Hintergrund kannst du nach der Verkleinerung ja wieder magentafarben auffüllen.
Außerdem: Wenn du Probleme mit den inneren Konturen hast, empfehle ich dir ein wenig mit stufenweisen Verkleinerungen (wahlweise bilinear, dann bicubisch - eventuell auch mal pixel) etwas zu spielen, um den richtigen Kompromiss zwischen Weichen Übergangen und dem Übriglassen von Details zu finden.