This happens with literally every single e-mail I get! I have to refresh Mail twice to make messages stay in my inbox, else new messages disappear and do the same thing the next time the iPhone checks for e-mails (which is very annoying because if I leave it it'll vibrate over and over again because of just one e-mail).
Restoring doesn't do it, and my iPod touch actually does the same thing too.
Restoring doesn't do it, and my iPod touch actually does the same thing too.