Better to be Heroku.com than Cloudhosting.com then and now. But I wouldn't want to be launching Del.icio.us or Flickr.com in 2011.
These days I think you're far better off with simple/short/spellable domains like: Fab.com, Batch.com, Groupon.com, Mint.com, Dropbox.com, Airtime.com, Oink.com.
For consumer-facing web companies these strike the right balance of credibility and hipness. You won't find domains like these unregistered. You'll have to buy them off someone.
For business-to-business companies domains are somewhat less important, names like: Mixpanel.com, KISSmetrics.com, Mixrank.com, Olark.com, Heroku.com will do the job perfectly fine.