PLEASE NOTE my update on this on 2009-Apr-05:
http://www.kornelius.org/index.php/blog/2-news/43-cleaning-the-asyncoperationbase-table-in-mscrm-4-pt-3

I previously posted about the asyncoperationbase-table in Microsoft Dynamics CRM. In the meantime I found out, that it would take several days with 100% CPU usage on our databases server to get all records deleted with the posted method.

So I decided to go into deep and do it myself.
I placed the following statements to the database to delete all completed jobs:

update AsyncOperationBase set deletionstatecode=2
where deletionstatecode=0 and statecode=3 and AsyncOperationBase.completedon is not null

delete from workflowlogbase where AsyncOperationid in
(select AsyncOperationid from AsyncOperationBase where deletionstatecode=2)

update DuplicateRecordBase set DeletionStateCode=2
where asyncoperationid in
(select DuplicateRecordBase.asyncoperationid from DuplicateRecordBase
left join asyncoperationbase on
(DuplicateRecordBase.asyncoperationid=asyncoperationbase.asyncoperationid and asyncoperationbase.deletionstatecode=0)
where asyncoperationbase.asyncoperationid is null)

update BulkDeleteOperationBase set DeletionStateCode=2
where asyncoperationid in
(select BulkDeleteOperationBase.asyncoperationid from BulkDeleteOperationBase
left join asyncoperationbase on (BulkDeleteOperationBase.asyncoperationid=asyncoperationbase.asyncoperationid and
asyncoperationbase.deletionstatecode=0)
where asyncoperationbase.asyncoperationid is null)

Using this article http://www.ascentium.com/blog/crm/Post98.aspx I tried to force the cleanup of the tables, but it did not do anything to the asyncoperationbase so I found this article
http://fkbase.info/index.php?q=node/16 telling me that the table won’t be cleaned at all. So I follow the instructions and placed the statement

delete from asyncoperationbase where deletionstatecode = 2

Finally this is the statement I punt into a maintenance plan „execute T-SQL“ job via Microsoft SQL Server 2005 Management Studio.

use CompanyCRM_MSCRM
update AsyncOperationBase set deletionstatecode=2
where deletionstatecode=0 and statecode=3 and AsyncOperationBase.completedon is not null and completedon< dateadd(D,-7,getdate())

delete from workflowlogbase
where AsyncOperationid in (select AsyncOperationid from AsyncOperationBase where deletionstatecode=2)

update DuplicateRecordBase set DeletionStateCode=2
where asyncoperationid in
(select DuplicateRecordBase.asyncoperationid from DuplicateRecordBase
left join asyncoperationbase on (DuplicateRecordBase.asyncoperationid=asyncoperationbase.asyncoperationid and
asyncoperationbase.deletionstatecode=0) where asyncoperationbase.asyncoperationid is null)

update BulkDeleteOperationBase set DeletionStateCode=2
where asyncoperationid in
(select BulkDeleteOperationBase.asyncoperationidfrom BulkDeleteOperationBase
left join asyncoperationbase on (BulkDeleteOperationBase.asyncoperationid=asyncoperationbase.asyncoperationid and
asyncoperationbase.deletionstatecode=0) where asyncoperationbase.asyncoperationid is null)

delete from asyncoperationbase where deletionstatecode = 2 and completedon< dateadd(D,-10,getdate())

Now I am waiting for the users to report any problems after doing all of this.
I wonder why MS did not implement anything to accomplish this, but perhaps the time effort using the SDK or bulkdelte led them to better put the problem aside.