CRMAsynchService not deleting the Records

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)