>Blocking and deadlocks are a part of life in the database world. Blocking to the point of timeout will have a serious impact to the concurrency of your application. Of course, I don't know of many applications that routinely delete 500K rows.

This application won't routinely be deleting 500K rows - I was just cleaning-up the database for further testing.