512x512 texture scaled up to 640x480 screen will look just fine, possibly with bi-linear filtering. Just remember that the big image is just the background. Draw your menu buttons, frames, fonts and all the sharp stuff on top of it.

Make sure you do the downscaling properly with good image software. Something like free Gimp can do it well. Have the real 640x480 background saved separately and scale it for texture image down to 512x512.

Also what you need to do is not having all 30 background pictures loaded to your program same time. Have 1-3 texture slots for backgrounds and load them from the disk (not per-frame but when screens change).