Wirelessly posted (BlackBerry Pearl: BlackBerry8100/4.2.1 Profile/MIDP-2.0 Configuration/CLDC-1.1 VendorID/100)
Obviously the pop and imap protocols support deleting... How else do your messages disappear when you download them on your desktop?

Without being a BIS administrator, I'm just guessing here, but I imagine the BIS keeps a linkage between a message Id on the mail server that hosts your mail, and the message it sends your BB. When you delete the message on your handheld and say delete from mailbox, the BIS server then sends a delete command to the mail server.
I'm pretty familiar with the mail protocols used on the internet and know this is easily done. Its all really much simpler than it looks. Hehe.
HTH