Welcome to shared hosting!
I'm unaware of any way to "speed up" the mysql databases themselves, as being randomly "slow" is part of how shared hosting works. You can always report it to support (via the Control Panel) though and see if they can help you out, or you can try to use some form of data caching to see if that helps reduce your database queries.
As to your second question - you can always use an external database. You just point whatever script/application you're using to it. Why you would have to "take it up" with your registrar, is beyond me, unless you're referring to changing your 'mysql.domain.com' address to the IP of the external mysql server?
Chips N Cheese - Custom PHP installs and the like!