That query took 12 seconds. That's a bit longer than I'd like it to take, but within the acceptable range. The execution plan looks like this:
The inner-most clustered index scan has been changed to an index seek.
Since this runs on a pretty tight loop, if there is a way to further reduce the delete time then I'd like to explore it.