I'm confused why the cloud is viewed as expensive. For managed hosting on a big name provider perhaps, but there are dozens of virtualization providers who are capable of providing power and bandwidth for unbelievably small amounts of money.
Sure you don't get the uptime, reliability, and support of a big name host, but it's usually good enough. From what I've gathered, twitter's growth has not been severely hampered by the fail whale, especially in the beginning.
Once you've reached critical mass, you can move on to a larger host. I think it makes sense to rent rather than own, especially if you're just starting out.