table locks are the killer here...

Lock escallation happens @5000 rows, keep batch sizes below this

select 1

while @@rowcount > 0

delete top 4999 from ...

(or something similar)

Also you're using SQL2008+. read up on "Filtered Indexes"

Create a filtered index on your main table that contains your PK, and filters on your delete criteria. This index will be used to determine your deletion candidates, and the overhead should be minimal as the delete candidates should only be a small subset of the bulk of your data.

You can even monitor the size/rowcount of the Index to trigger when to start the purge - to keep the performance hit to a minimum. (or delay the start to an off-peak time) rather than using a scheduled date/time.