I am currently using a
VPS Hosting but don't yet have any great database heavy examples up there, but I do know of
http://www.find-a-videographer.com/ which is hosted on an eUKHost Linux
VPS Hosting-02 server.
This is a rather busy web site hosting which performs a lot of MySQL Server queries. For example; each time a change is made on the select elements a MySQL Server query is performed to get an xml list of appropriate regions/locales, this is even before the search is performed!
I looked after this web site hosting for quite a while with no speed problems.