It's a known problem that we're currently working towards resolving. I'll open a Service Status thread for it.
The problem affects people who tend to access their email using both POP3 and Webmail. I also reckon it'll affect anybody electing to leave copies of their messages on our servers.
find that you can remedy the problem by deleting your mail account in Windows Live and running through the setup again.
The problem has been caused by a discrepancy with the UIDL numbering of messages after a migration from one mail collection platform to another.