Perfect Resize (formerly Genuine Fractals) is usually considered as one of the best available upsampling tools for photography. It is worth trying.
Another, actually the opposite approach might be to use strictly multiples of the original size (like 2x = 640x480) and use the simplest thing - nearest neighbor algorithm that will just make the pixels look like squares. The images will be pixelated, but crisp.
If it was me, I would try both methods on multiple images and asked people what they think looks best.
Edit: One method, that is not very useful in regular photography but might work well in this case is vectorization.You only have as much detail as the original picture, but you can enlarge as much as you want.
The following images are (1) up sampled from 200px to 800px by nearest neighboring (2) Vectorized from 200px x 300 px original. I chose very small size for the original and they certainly look wrong when used on regular photograph, but they show the effect well.
