I'd say go with expencive xen VPS, you get guranteed resources and the power to change your kernel, basically a dedicated server which can be reinstalled with few clicks without need to contact/wait for anyone.