Thanks everyone for the suggestions. I've made some big improvements to the site in terms of loading speed and I thought I would let you know what I did. The site has information about Nerja on the Costa del Sol in Spain, including holiday accommodation, which makes up the bulk of the pages and the bulk of the processor overhead. As such it has around 1000 pages, mainly created by custom PHP scripts from custom field data. The data for the rental properties is largely taken from the estate agents own databases, so the pages are created automatically (the script for this runs at night).
1) Rather than just turn off plugins one by one, I installed another plugin called "Debug Queries" by Frank Bültge to analyse my db usage. I used this to identify which plugins were begin wasteful with resources and I then got rid of the worst offenders. For example Adrotate was making 28 database queries to display two banners - that was more than 50% of the queries on the page. I wrote my own much simpler version of Adrotate which has 0 database queries and does pretty much exactly the same thing.
3) I tried various caching plugins but none of them were really flexible enough or effective enough to do what I wanted, so I decided to add my own caching code. The pages are created by custom PHP scripts, which build the pages from the database. Now the first time a page is rendered a copy is saved as a file on disk. Subsequent page loads come from the disk. This reduces the processor time by a factor of 10-20 (ie processor time is between 5-10% what it was previously). By writing the code myself I have the advantage of knowing exactly which parts of the page stay the same and which change, so only the static parts get saved to disk, plus I know when the cached versions need to be updated.
Overall On a typical page I reduced the number of database queries from 50-100 to 5-10 and page loading time from 1-2+ seconds, to under 1 sec on average.
I also tidied up the database in a few ways. For example Wordpress is quite wasteful in the way it uses the DB and keeps copies of all sorts of things in the DB that you don't really need. So I used a plugin called "Revision Removal" to remove page revisions from the database. I removed 4000 or so revisions in this way (I have 1000 or so posts in my blog) - database reduced in size from 1.5Mb to 1Mb. The comments are also quite wasteful of resources and I tidied these up as well (google for more info on this).
Finally I moved to a different host, and I am now finding page delivery is much more consistent without the yawning pauses (sometimes 5-10 seconds) that sometimes occurred with the old host.
If you want to have a look at the website this page http://mynerja.com/rentals/nerja-long-term-rentals/ is one of the heaviest resource users (at least it was before I wrote my caching code). It shows a list of all the rental properties on the website. If you look at the bottom of the page (just under where it says "Nerja Long Term Rentals") you will see it says "Took 0s" if you are seeing a cached version. That is the amount of time spent doing the database queries - without caching its about .3 -.4 of a second. At the very bottom of the page you will see the total number of queries and how long the entire page took to render. When I looked just now it showed "23 queries. 0.690 seconds." which is pretty fast. Before it routinely could take 2 or 3 seconds to load.
One other thing, I also cached the header as I found the query to construct the navigation menu was taking far too long for something that is exactly the same (more or less) on every page. I used a str_replace on the cached version of the string returned by wp_list_pages() to get the current_page_item highlight back. In all caching the header saved me over 0.5 of a second on load time - and remember as it is the header, it is on every single page.
Overall the work was well worth doing (even if it did take a few weeks :D) and I hope this post gives some ideas to other thinking about optimising their wordpress installs.