hab zwar keine erfahrung mit den internationalen angeboten, aber 1und1 / united internet ist ja an sich ne ordentliche marke. nicht ganz billig, aber durchaus noch vertretbar (und hey, bei den dollar-kursen ...)

http://order.1and1.com/xml/order/ServerRoot

obwohl natürlich wieder lustig, dass sie "Access to Google Webmaster Tools®" als feature ihrer server anpreisen ;)