I know that Hotmail empties their deleted email folder a couple of times a week. I assume that MSN is the same way. My best guess is that they empty their "deleted items" then you connect and attempt to get new emails it will sync up your folders to theirs and voila! Those emails are now gone.