When we started DotSpots in 2007, we leased physical servers from iWeb. It was far cheaper than EC2, but you lose of ton of agility when you can't pave a server and rebuild it from the command line. We switched to EC2 and starting paying a bit more, but we've been able to expand capacity much more nimbly than before.
The only thing I'd recommend running outside of EC2 would be memcache, but that's only if you're really pinching pennies. If you're an early stage startup and you're not running virtual machines, you might be doing something wrong (IMHO).