Weird,
I made a rule that moves (a copy) of every send message to a folder (Deleted Items) right after sending it. If moving the message itself can't be done, move a copy and delete the original message. Worked fine for me.
I used Outlook XP with an POP3 account. Couldn't test it on Exchange since our corporate FW is down
