Those can be a little hard to find sometimes. If you want hosting on a machine that provides good transactional integrity, you could look at going with http://www.commandprompt.com/ They only support PostgreSQL, and are $29.95 a month ($329 a year) for a basic account, but they provide nice SLAs and a solid environment.
Compared to the prices listed here:
http://solutions.mysql.com/hosting/rackspace.html
($3250 to $15,600 a year)
That's actually pretty cheap.
You get your own postgresql instance, completely yours, no sharing, and the base account is only.