0
Hello Patrick,
A number of things.
A. --- Why is it trouble to set up MySql on each of your clients machines, It is not that difficult to completely automate the process in a setup scenario and add the necessary DSN records to the registry.
B. --- Most if not all hosting companies will allow direct access to your MySql database using MySql Administrator, MySql Query Browser, I know godaddy.com does and so does Hosting.com (formerly hostemysite.com) but that would be to only one MySql Database.
C. --- Security would be an issue however.
4. --- Having said all this, if you want multiple users connecting to the same database using an on line account from a desktop application you can do it this way. Create a web interface where you send all your requests to the web page where security is / has been established then you marshall all your requests via your web site, this is in fact how my Desktop Organizer (a desktop application) product determines if an installation on a machine is registered or not.
The impossible is only impossible because you think it is, open your minds,

0
You can search the internet using something such as:
"external connection" "sql server" host
That should at least show that it is possible. You might need to send an inquiry to some hosting companies; they don't all specify in their web site whether they allow external connections. I assume you understand that the reason to not allow external connections is to ensure security, but I don't know how much of a security threat that external connections are.