In a vain effort to try and eck some speed out of our host (Streamline.net - poor quality but cheap!) I have been bugging them about the speed of the databases.
In the end - and credit to them - they relented and have moved us to a new server. Time will tell if it's quicker (but it's lunchtime and the forum hasn't gone a crawl so it looks positive so far!).
But if you find any problems, please let us know.