You mention MySQL hosting, I don't know if I've got this right, but I understand that some hosting companies have stopped letting people have access to MySQL directly, they only let you have access to it if you are using, like, WordPress.
I said I'm not sure if I've got that right but I'm sure I read that somewhere recently! If it is true it's worth making sure you can get the access rights you need before you sign up.
By the way I use 4D Hosting. http://www.4dhosting.com/
I have always found them helpful. BTW - it might be on their website where I read about the MySQL issue!