They kept on asking me "Do you have any third party software running on your server?" To which I always replied no.
They then insisted on sending me a sample of the log file again, which was just reams of queries and times and dates and no use whatsoever. One thing I could construe, however, was the user account generating these queries. So what I've done is delete that user, then setup another user and given it limited permissions and used that account in the included inc_db_connect.php script I use. All pages on my site use this page to connect to the DB server so they should all now use this restricted user - but not restricted to the point of stopping my site from working.
One interesting thing I discovered since posting my original post is PHPMYADMIN has a DB status page which shows the number of queries run between certain dates. Apparently 32k Created_tmp_disk_tables queries have been run which seems awry to me. None of my queries should be creating temporary tables so I wonder if something untoward has been doing this and causing the problem.
I'm starting to double check my indexes. What rules should I follow when determining indexes? Just index fields used in queries often?