Thanks for the tip. I already have a Linode vps actually and it is great. I should have been clearer however, I'm really looking for a managed service.
My client will pay, so I'm looking for something that will still be around when I've moved on to others things. And the hosting firm will take care of patching, backups etc..