We've been on dedicated servers for a long time, and we're at a point where cost-efficiency and flexibility are our two biggest factors.
We're expecting pretty linear growth, so scaling isn't a huge deal. Up until now we would regularly switch to a better server, stay there until we outgrew it, and then jump again. It's kept us relatively lean/current and our costs have stayed low as the cost/quality of hosting has changed (and we've gotten better at sniffing out good hosts).
Places like linode and slicehost would have been decent options in the past, but we serve 1-2 TB of data each month, so we like to have lots of bandwidth available. And while many dedicated servers offer that, our server admin is pretty picky about the hardware, so she'd like to be able to manage it on her own.
Out of curiosity, how easy is it to 'hook up' two separate Xen instances, assuming Xen is what slicehost and Linode run on? I'm not a server guy, but I actually share a slicehost plan (separate from this particular venture) with one of our fellow News.YC hackers, so I'm familiar with how excellent the company/service is. If they're really that easy to connect/scale then it might be worth the extra cost...