Okay, I've decided that a VPS will do for this application. I'm looking at these outfits:
http://adiungo.com/vps/
http://defenderhosting.com/vps/
http://servint.com/vps/
Anyone have any comments about any of these companies, or any other recommendations?