It just goes to show that you should always think about the big picture. After I went back to the DBA and complained about the speed it was discovered that one of the foreign keys used for joining was not indexed. Adding this index speeded one of the cascaded deletes up from 3-5 seconds to "very quick".

I now have reasonable speed from the SQL calls but my problem still lies in the fact that it can take hours to apply a "big" update which I have just been told is around 110,000 records.

I am therefore still looking for some way to increase the performance of my code.