I believe MediaTemple’s Grid Server ($20/month) is up to par spec wise to support Magento. I have a dedicated server with them and have to use the PHP5 CGI binary until I upgrade the php version myself or they do. Either way, (mt) does support Magento.
For any UK users out there, I recommend Heart Internet. You just have to add a line to the top .htaccess file to tell it to use PHP5. I’ve had no problems so far.
hey guys i also wanted to add, i read that simplehelix had included it as an auto install, but cant remember where at i read this, this forum for sure tho