This is one from the SE referrals in my logs.
There does seem to be a problem deleting messages when an account is set up as IMAP. The “empty deleted items” option doesn’t seem to delete the messages from the server, and they come back with the next sync. I’m not sure of the technical details, but in Outlook, deleting messages from an IMAP account is a two-step process—first, the delete, then the Purge Deleted Messages. The empty deleted items on the Treo seems to be only the first step.
I have no problems deleting messages when I reconfigured the accounts as POP3 accounts.
<update 2006–07–30>
If you want your IMAP to work properly, look into FlexMail. FlexMail is a complete replacement for Pocket Outlook, and then some. IMHO, FlexMail handles IMAP accounts better than desktop Outlook does. In addition to properly deleting items in IMAP accounts, FlexMail will perform POP before SMTP, which is a requirement to send e-mail on many hosts. Pocket Outlook does not have this option.
If you sync to an Exchange server, set that up in Pocket Outlook and let FlexMail automatically import the settings. If you have POP2 or IMAP accounts alreadey set up in Pocket Outlook, just delete them and set them up again in FlexMail, since there are more settings for these accounts than are available in Pocket Outlook.