The logic seems to be OK. Probably hit an MS issue. You are talking about M - millions of rows?
Microsoft introduced DELETE TOP 50000 (or other) ....with SQL Server 2005. This is supposed to be reliable.
Another way to delete is select * into what you want to keep combined with renaming. It maybe faster.
Kalman Toth, Database, Data Warehouse and BI Architect
The Best SQL Server 2005 Training in the World