I recommend
4webspace (Tera-Byte). They offer a Cobalt RaQ3 Server with 512MB Ram, 10GB harddisk, and 100GB bandwidth for $99/month (no setup fee []
https://www.ubbdev.com/threads/php/images/icons/smile.gif[/]). You have root access to the machine, that means you can install whatever you want (PHP, MySQL, or just the latest Apache Server).