FMS & storage

I am looking for a host that offers Flash Media Server (or Red5) to stream videos. But the hosts I find with FMS don't have much storage and vice versa (the ones with decent storage don't support FMS or have root access). So that defeats the purpose of being able to stream videos if I can't have that many on the server to begin with.

So I was wondering what people do to have a site with a lot of videos and FMS. Just spend hundreds of dollars each month and not have much storage? Or build my own server, which can also be expensive and is time consuming? Any insight would be appreciated.