GO!NotifyLink Enterprise Server:

When accessing email from IMAP servers using certain email clients, such as some Outlook connectors, the mail is not deleted from the account at the time the user marks it for deletion. At that time the email is only marked to be deleted, it is not actually removed from the account. Once this is done the email actually needs to be expunged from the account. This is done on the back and is not a command that the end user sees. Many users with Outlook clients are set up to expunge deleted email when the Outlook client is closed. The email will not be shown as deleted on the device until it has been expunged from the account.

This is scheduled to change with the release of our 4.5 client. In this upcoming client the GO!NotifyLink server will support the ability to recognize an email has been deleted once it is marked for deletion even before it has been expunged.