Take care with PHP/MySQL on those shared hosting plans. I would recommend read essential php security by chris shiflett. One of the books that made me switch from shared to dedicated at once.

Now back to the legal part. You can distribute the required dll's with your software, but you need to put proper c&c in your credit/copyright. At least this is what has been told to me when I worked on the plugin from Destop. I refer here to the community release of MySQL and no other products.

Atomix. I don't understand why you need different MySQL servers. I guess you need them as fallback? Maybe you can write a polling script to check if the server is alive and if not try the next one. So with the line of code above you should be able to get a 0 or 1 and go from there.