I was in the same situation a few months back and I remember reading about mounting an Amazon S3 Bucket on a VPS. Did you consider that?

I never actually went through with the idea, but it's definitely on my things-to-do-when-bored list!