with POP3 email accounts, there's no sync so when you delete an email, it takes it off your phone but it's still there on the server.
Don't know why you're getting this as usually the only time I see my "deleted" emails again, is when I install a new ROM and it's a fresh check.
I have 2 go 2 the actual inbox of the account (MSN) using the browser &, either read & move or just move 2 another folder then mark read or delete notifications from my phone email app. Gmail is the only mail I can quickly handle in 1 process. I think it works this way 2 try & encourage us to use gmail more & we had to create the account if you didn't have one just 2 get the device & contract. Incredibly time consuming having 2 sometimes send email 2 my self just 2 get my information do what I want it 2 or 4. I'm hoping the update with the corporate stuff smooths some of the authorization either way its not as seamless or easy as I think it could or should be.