Microsoft now cares about the problem I posted here:
http://www.kornelius.org/index.php/blog/2-news/37-cleaning-the-asyncoperationbase-table-in-microsoft-crm-4-part-2

Just execute the following KB articles in the order posted:

http://support.microsoft.com/kb/961768/EN-US/
http://support.microsoft.com/kb/957871/EN-US/
http://support.microsoft.com/kb/968755/EN-US/
http://support.microsoft.com/kb/968520/EN-US/

Please note the last action can take quite a while. I changed the row

Select @DeleteRowCount = 2000

to a much higher value

Doing so all workflows etc. are delete right after their (successful) completion. The only thing remaining are matchcode updates. I’ll think about handling them with bulk deletion.