Well, in short, the EASIEST way is to use the Enterprise Server as it already runs as a web service and you can put it anywhere, hosted or otherwise, WITHOUT the requirement of a VPN and all you have to change is the connection within your AppMain.vb to use the EnterpriseDataSourceItem instead of the SQLDataSourceItem.
That is the sort answer, but let me tackle your questions.
1. What is the simplest way to deploy updates to the remote users? Over internet?
If you are referring to program updates, then yes. If you have the need to be able to automatically update your clients, then the web will always be the easiest solution. If you want to automate this process, then you will have a web service that your application talks to every know and then to see if there is a new update. If so, download it and install it. Pretty basic. But if you are talking about SQL updates, it will be more dependent on where your SQL Server will be hosted. SQL updates will require more security and a bit more discussion if this is your meaning on the question.
If over the internet, would I host the updates on a ftp site that the remote users would download or have some way that the app automatically downloads the update?
Ftp or Http, either will work depending on your needs. It is actually easier in some ways to program for http versus ftp because depending on where you host your files it may require a TFTP client, which is totally doable, just a bit more work. So in short, you would get a site hosted by GoDaddy (or someone like them, we actually have started using them for more and more and it has worked pretty well). Then you would create the web service that I mentioned, not hard, I promise...that accepts a version coming in and then sends back a response whether there is a new version for download or not. We do this very thing with our medical application and even have the ability to send out updates to specific customers so that we can test things out and not have the entire user base down if there is an issue. But the application sends over the version that it is on, then it checks with the server, if there is a new version then the response will give the url location of the download. Download the file and shell it (launch it) and that is pretty much it.
Should I use a hosting site for the SQL Server Express databases so that I don't have to support 10 VPN connections?
This would really be entirely up to you. If you do not want to deal with a VPN, then yes, you will want to host this elsewhere. However, if you do this, then the TDS stream (Tabular Data Stream - the SQL formatted data streamed between the server and the client) is pretty fat...that is why we created the Enterprise Server. If you go this route, I would highly recommend the Enterprise Server!
If hosting the SQL Server Express databases on the internet is the way to go, do you have any suggestion on who I should use?
Again, this is up to you, but we have used GoDaddy for some things lately and aside from their horrible marketing...their services are nice. I have not tossed an ES up on their servers, but I see no reason why it would not work.
Also, if am going to host the databases on the internet, how do I make the connection using SF?
Using the ES it is just a few lines of code. But if you are going to use straight SQL connections, then you will have to expose a range of dynamic ports and port 1433 (by default) so that you can connect to the server on whichever hosted server you choose. If you use GoDaddy, I am not sure you can do this. You can do this with your internal servers for sure as you would have control, but GoDaddy is pretty restrictive on these types of things. So I am not sure if it would be possible or not.