Ok, I went around, asked some friends and managed to cut out this sort of thing:
http://www.hostengine.co.uk/shared-hosting/shared-mysql-hosting.html
Here, a very decent hosting company, renowned in the industry for being pretty expensive, but provide a very good service. Their services (I have heard) are top notch and their PR at Google appears to be quite high.
The Free MySQL host you spoke about earlier, would probably be sufficient for you needs, but if you plan to have a Forum or a MySQL-powered website, it wont serve you well. The chances are that their servers are highly volatile and as you can see from the page on the other end of that link above, they do have data refreshes and mistakes do happen. Thing is, I doubt there is backup falicities and thats a problem.
You could also just ask a friend who happens to have an account with someone else whether their server will accept incoming MySQL connections. If you were in this country with local traffic, I would give it to you, as its very little server strain and usually not a security risk. But I'm only on a VERY VERY slow 128k piped link and my servers struggle with international traffic already.
Good luck finding a host who can suit your needs,
~Equinox