Provision Host is working well for me.
Quick run down of what you get that I can think of right now:
Free subdomain.
Free access to McMyAdmin Enterprise (with all but the lowest server subscription).
Root access to your server running CentOS tweaked for MC.
Java 1.7 installed.
Apache2 installed.
Bandwith, CPU and Memory usage charts with the ability to restart the server instance through their web page.
MC server auto starts when the server is started (unless you disable it)
SSH, FTP and SFTP access
Anything else you like as long as it's minecraft related since you have root access to setup and configure the server in any way you like.
I like using the SSH console with Putty so I fetched and built from source htop to monitor usage, modified the webserver, set up dynmap and did a few more tweaks. It's almost like running a server from your own home (wich I did before) except you don't choose the operating system and you don't have physical access to it. Subscription changes are very fast and automatic it seems (I could see the increase in memory jump up dynamically in htop through both of the upgrades I've gone through and they were done within the hour after immediate payment).
Server locations are in the US, Canada and UK.
Their staff has also been positive and helpful in their communication so all in all they are a host I feel safe in recommending without having reservations.