Virtualis hosts servers with MySQL, PHP, and much else upon request. I'm a reseller so if you have questions let me know.
You can check out
http://www.virtualis.com/vr/rharrell
Tech support is excellent, and their dedicated server packages are really nice.
