Given this is a Mac question, I thought I'd start where all the Mac readers might be. We're evaluating Macs at our school district, so this is the first one I've worked on. I'm running on Leopard.
I have iSync up and running with no problems, so I turned my attention to the Mac Mail app. I have it set up to use IMAP for syncing. It works fine, and if I delete something on the MacBook it disappears from the Zimbra web interface and vice versa. However, if I open Outlook on my Windows workstation, all the mail I deleted shows up in my Inbox as read messages.
In Mailbox Behaviors for this account, I have checked "Move deleted messages to the Trash mailbox" and unchecked "Store deleted messages on the server." Changing the latter box didn't seem to make a difference. I have "Permanently erase deleted messages when:" set to "Quitting Mail."