Wow, talk about not seeing the forest for the trees. All three queries finished instantly, each using a index seek. I've altered the DELETE statements, and I expect it will have a marked impact on performance.

Thank you so much for the help. So glad I could get another perspective on this.