As I said before, your choices in 2000 are more limited. Filter the data on additional criteria to reduce the batch size so you're deleting in smaller chunks and providing the optimizer the ability to come up with a good plan. Using ROWCOUNT doesn't change what the optimizer chooses and if the filtering criteria is not there, the optimizer will choose to scan the data, which is slow.