After having read my mail from IMAP I noticed that the mails I had deleted were still in the folder on my desktop client (Thunderbird). Now that's strange but obviously noting new if I refer to this bug. Impressive to see a bug in a core application open since 2008!
So I followed the recommendations in multiple forums and installed K9.
And now I'm happy again:
Well that's a five stars from my at Android Market for K9…