@MonsterAxe
I tried first with SP1 RU3 whithout the Registry key metioned in kb/2009942 - I deleted items and it took a time until this was shown in Outlook. So the error still occured.
I addedt the "ParametersSystem" Key and the EnablePushNotifications Entry on the CAS Server. Then I rebooted the CAS Server. Deleting items in the Mailbox shows now up in a timely manner.
The problem still occoured with Public Folders. I added the key on the mailbox/public folder server and rebooted this server. I am not shure if it is working correctly now concerning the public folder. It still takes about 5 seconds until a deleted mail is gone.
But I dont get these errors "the element you want to delte is not here"