It's frustratingly difficult to find a high-storage VPS at an affordable price. This announcement by Linode is a start. But I think the market has a ways to go yet.
I never actually went through with the idea, but it's definitely on my things-to-do-when-bored list!
I'm with http://budgetvm.com/ myself because for the same price (as a BuyBM box), you get a ton more RAM and CPU. The problem here is they're running OpenVZ, which among other things, doesn't support certain iptables (firewall) functions.
Also you sacrifice disk space. But for the application I'm running (Riak cluster), memory is important too.