This is typical of how IMAP servers work - deleted messages are marked as deleted but kept in the inbox until a separate process actually removes them (called expunge). Most mail clients have a way of hiding messages marked for deletion, but the me.com interface doesn't. On me.com when you go back and re-delete the first deleted message, that forces an expunge. I would think it would be very easy to implement this on me.com, if anyone can ever get the programmers attention to do it. I've sent two support requests in on this, but been ignored completely by Apple. If a programmer would just spend 10 minutes on it, it could be fixed. Just filter out the messages marked for deletion from the display and add an expunge button (or just do an auto-expunge). Most IMAP clients have this built in - Thunderbird, Outlook, Outlook Express, etc.