1. First, Check event logs to make sure that there is no issue with the "CRMAsynchservice"
2. Second, ( very important ) make sure that you have installed all the CRM updates(http://support.microsoft.com/kb/949256)
3. Third, Make sure that you stop Any "Duplicate Detection Jobs" I find out these jobs interfere with the bulk deletion.
4. If everything fails, contact microsoft dynamics Forums: (http://social.microsoft.com/Forums/en/crmdevelopment/thread/919a62fd-c629-48be-a7fc-329afbd2b04d)