In one of our migration projects from 4.0 to 2013 we experienced the issue, that we couldn’t clean the AsyncOperationBase table
with the common cleaning script you can find for example here: http://crmknowledge.wordpress.com/2013/03/24/31/.
This leads to time out issues during the redeployment of the migration database.
We tried to set some indexes, but that did not help and it lasts ages to delete the no longer needed AsyncOperation records.
After some research we found out, that the reason for our problem was the huge DuplicateRecordBase table.
The following blog showed us a way to solve this issue http://www.powerobjects.com/blog/2012/01/20/crm-2011-large-duplicaterecordbase-table/
The recommendation was to just truncate the table. After we did that the cleanup of the AsyncOperation table worked well.