Which email service provider you are using? I suggest you to use only gmail with them because I have never got such problem with them when using gmail address. Have you checked SPAM folder or Archived folder?
I am using Live, is there a way to change it and keep the account?.