If your hosting provider is a Windows hosting provider then a) they need MySQL installed & b) they need to have the MySQL ODBC database driver installed for .NET applications.
http://dev.mysql.com/downloads/connector/net/5.0.html
Edit : having read your post I see you're interested in MySQL hosting, not web application hosting.
Are you putting your application on your host? Or are you running the application from somewhere different than the MySQL hosting is located? If the latter then your MySQL hosting provider will have to allow external access to MySQL, which some are reluctant to do.