Well, after the last fiasco with MediaTemple's hissy fits, we took the plunge to trial a new hosting provider - SliceHost. Where MediaTemple protects you from the inner working of the services and servers you buy, SliceHost just drops you in there and lets you tinker directly withe the server itself. I can choose the operating system, reboot it, and install whatever I want on there.
Anyway not getting into the nitty gritty, it took just over 2 days to set up and using an old domain name we set up the myfolia site on the new SliceHost server just to test it out. One thing really stood out - it's fast. Blindingly fast! Pages load so quick you don't even realise that you're clicking on them. We're a little disappointed we didn't do this sooner :)
So - we're going to do a bit more testing and will be looking into moving over the site to the new server. But we'll keep you posted on that.