We have SQL servers hosted with two different providers that we are happy with:
Both of these have been very reliable in production for 3 years or so. SoftLayer offers more services and a richer self-service portal. Database Mart is less expensive.
Note that we have not had either company provide database mangement services: we have managed the servers ourselves. (Physical dedicated servers.)
We have also worked with Saca Technologies who have provided a managed SQL server environment as well as management services of self-hosted servers. They have been good to work with too, though their primary focus seems to be on hosted desktops. They tend to use virtual servers, but if you have specific requirements be sure to clearly outline them and they will meet your requirements.