i have a blackberry 8100, running on a BES 4.1 server, i had a user who was using a old handset and was upgraded to the 8100, i did enterprise activation, a few of his emails came through on the blackberry, i sent a few test emails, all seemed fine until about 30mins later the emails i had sent and a few others disappeared, wiped the handheld and setup again on the bes server, same thing, removed from bes server and added again, still emails were deleting from the blackberry, added myself to the bes server, enterprise activation using my email, tested for 24 hours all my emails were there and none deleted themselves from the blackberry, check the security permissions between my account and the users account no difference
I'm surprised that as thorough as you were with the trouble-shooting, you didn't perform a simple search on here. Your issue is well known and has been addressed many, many times on here;