How to make a Desktop Application developed in .NET C# access online database?

Question

I am getting a software prepared from a Software Firm. The proposed software needs to access online database residing on a server. I have got a Windows hosting plan on that server with MS Access (*.mdb), MySql4 and MySql5 database options. Now the Software Firm is saying that a desktop application cannot access online database unless there is MS SQL, for which I have to upgrade my hosting plan. I would request you to kindly guide me by answering the following:

1. Is it true that a desktop application cannot access MS Access (*.mdb) with ODBC unless there is MS SQL on server?
2. Is it true that a desktop application cannot access MySql4 & MySql5 databases on srever?
3. Is creating a webservice the only option for easy link betwen a desktop application and an online database? (if yes, is it a very big task requiring a lot of money?)

For now, these are the main questions that I have in my mind. After your valuable replies, I will take a decision as per your guidance.

My knowledge about scripting:

1. ASP for developing webpages with data access - Rating: 3/5
2. VB for desktop applications - Rating: 1/5
3. .Net (both for webpages & desktop applications) - Rating: 0/5

I am eagerly waiting for your solutions.

Thank you,
Pavan Kumar