I have a VM with 400 gb storage for €5/mo, from xenpower.com. I think I got that price on a promotion; it seems to be €9/mo normally. I have no particular reason to trust that provider, so I use it only for encrypted backups / annexes and data collection.

It's been ok so far except for the time I was trying to get pv-grub installed and broke their remote console and had to reimage and re-backup 100 gb of data since they wouldn't fix it. You get what you pay for I suppose, but this let me test that my propellor configuration worked reliably. ;)

backupsy.com is another VPS provider in the cheap storage space that's perhaps better known/more trustworthy (but has a much more restrictive TOS limiting it to "backup only").