Not sure on the validity of (nolock) on a table where you are deleting data?
That aside, you mentioned this has worked in the past, but not so well now.
What you don't state is other contributing factors like
* Volume of data involve on both the related tables
* Is there an RI link and has that any supportive indexing to help the query.
* What sort of number of deletes are you expecting, ie When originally run a few rows to be deleted would not have the same impact as say several thousand.
As with a lot of the forum items on this site (I know because I have asked questions as well), it works a lot better if you can give as much relevant details on the issue as possible.