>That cracked it. It in fact did make the query faster, there were more deleted records in the table than I realised.
Be careful. It is my experience that an index on deleted() can make local queries (not over a network), and with few records, faster; but the same query over a network, and with many more records, might actually get slower. Before deciding to keep the index on deleted(), you should test under real-life circumstances, for instance, over a network and with the number of records you expect to have in the near future.
Difference in opinions hath cost many millions of lives: for instance, whether flesh be bread, or bread be flesh; whether whistling be a vice or a virtue; whether it be better to kiss a post, or throw it into the fire... (from Gulliver's Travels)