We run Exchange 2003 as a virtual server using Hyper-V. Recently accidentally formated the drive on the host server containing the virtual servers, including this exchange server. Recovered using backup, and everything is fine, except some users are not getting any incoming e-mail. No internal mail or external mail. Cannot see the mail when logging in through OWA either. However, the affected users CAN send e-mail to anyone. In our total organization, I would say 80% of all users are totally fine with e-mail function, while the other 20% can only send but not recieve. It is not the Outlook clients. Any ideas?

Has the Exchange server kept the same IP? If your firewall is routing SMTP mail from the internet, check any NAT rules.

Easy way to test is to telnet your MX record on port 25 and see if exchange responds.

I've seen some ISPs spam filter mail which can explain why some users can recieve and some can't, so best way to test is to send SMTP mails using Outlook Express or Telnet etc right into your Exchange public facing IP.