Using BES, and have more than this user using a blackberry, however only a couple are having this issue. therefore it leads me to believe is on the users side, not the server side. However I am not sure what 'it' is.
Not sure about wireless reconcile, he is using a .pst files, not sure about read and unread status, not sure about deleting from outlook and deleting from the blackberry. Not sure about wireless reconcile off from the server as well, although I 99% sure its on.
I am assuming wireless reconciliation is turned on because he is getting email updates on his handheld, its just not deleting it in Outlook when he deletes it from his handheld.