The problem is that the default behavior for people who use an IMAP client is for "delete" to actually mean "keep a copy in All Mail." The server will also give a false OK status to the client following the EXPUNGE command (see the IMAP4 RFC for details), so the user is not alerted to the fact that messages are not being deleted.