As it turns out, Exchange is changing the IMAP message ID every time one of the above actions occurs*. This causes RIM to see the message as new and re-transmit it to the handheld.
The options to fix it are..
Switch BIS to POP3 instead of IMAP. But then deleted items sync won't work.
Switch to Blackberry Enterprise Server. $5k in software fees, more depending on your user count.
Switch BIS to OWA..
That last option is the most promising. Unfortunately, with Exchange 2007 and forms based OWA authentication (the default), the normal url https://example.com/exchange doesn't work. Neither does https://example.com/owa.
What does work... the magic bullet for BIS+OWA on Exchange 2007 is..
I have not found this tidbit on any forums or documentation, and I really hope it helps someone.
* Constructive criticism for Microsoft.