What we did for Return to Dark Castle (which ran at a fixed 640x480, 16 bit color) is give the user the option to scale by nearest neighbor, interpolation, or both (mixed 50% with each other). The "both" option worked surprisingly well, especially since it was a "quick fix"!
