Never seen it. But I'm still thinking of some local add-on. Anyway, it might help to see if it's the PC that's doing it or if it's the users profile.

If you can reproduce the problem (find a mail that consistently disappears into the deleted folder on the affected PC's) see what happens if:
a) You send it to the same user and he logs on on a 'normal' PC.
b) The regular user of a 'normal' (you as administrator, for example) logs on at an affected PC.

If only the user is affected and not the PC, delete his profile and remake it. Than the problem should be solved.

Hope this helps.