I recently signed up with "ev1servers":http://ev1servers.net. I'm now the proud parent of a dedicated 2Ghz Pentium 4 box. What's better is that I originally signed up for a 1.3Ghz Celeron!
Not many weeks ago I signed up with site5 shared hosting. They aren't bad, but shared hosting by it's nature forces too many restrictions for an application like msgpad. I'll stick with the site5 host for my blog, and backup dumps of msgpad though.
I looked at ev1servers, aplus, serverpronto (who I signed up with once before), and serverbecah before choosing ev1servers. They were hands down the best. You just have to check out their "data center":http://www.ev1servers.net/Datacenters/ to see how serious they take their business.
It came down to winning my trust. ev1servers provide serial/root console logins for every single box they run! So if _anything_ goes wrong with the box, I will always be able to sort it out (provided it doesn't explode I guess). When you're not able to physically touch the box, that type of feature is a necessity.
Anyway, now I can run my MSN identity validator on the box, postgresql (yes, you win Michel;), mongrel, and all sorts of other custom processes I couldn't run with shared hosting!