I had a similar problem and still do! Sometimes I dont get a notification for new emails or when a contact signs in. I emailed Messenger trouble shooting and they said it could be that my IE settings were hijacked. I tried what they recommend but it didnt seem to work.