Android mail client not deleting emails on IMAP server
Unbelievably this bug is still outstanding as of Android 4.0.4.

http://code.google.com/p/android/issues/detail?id=1029

The only fix for this is to use a different email app. Most people end up switching to GMail.

Not happy. I miss my Nokia N900.