That's the way that this device interracts with IMAP servers. I spent a lot of time trying to track this down. Finally in the manual I found it.

Outlook Email
E-mail messages in the Inbox folder in Outlook will be synchronized automatically with your PPC-6700. You can elect to synchronize additional folders by designating them for synchronization. The folders you create and the messages you move will then be mirrored on the e-mail server. For example, if you move two messages from the Inbox folder to a folder named Family, and you have designated Family for synchronization, the server creates a copy of the Family folder and copies the messages to that folder. You can then read the messages while you are away from your PC.

Text Message Account
If you use a text message account, messages are stored in the Inbox folder.

POP3
If you use a POP3 account and you move e-mail messages to a folder you created, the link is broken between the messages on the device and their copies on the e-mail server. The next time you connect, the e-mail server will detect that the messages are missing from the Inbox folder on the device and will delete them from the e-mail server. This prevents having duplicate copies of a message, but it also means that you will no longer have access to messages that you move to folders created from anywhere except the device.

IMAP4
The folders you create and the e-mail messages you move are mirrored on the e-mail server. Therefore, messages are available to you anytime you connect to your e-mail server, whether it is from your PPC-6700 or PC. This synchronization of folders occurs whenever you connect to your e-mail server, create new folders, or rename/delete folders when connected. You can also set different download options for each folder.

Now consider the implications and what is being said. Email messages are mirrored on the server. The server is doing the job of synchronizing. As far as it is concerned, YOU JUST MOVED AN EMAIL MESSAGE. That's why you get the message back the next time you sync.

I still believe it's a flaw in the device software, but that's why it doesn't stay deleted.