I'm having the same issue with one of my ISP2 servers.
The server operated without any issues for over 3 months now. About a week ago, I have started receiving complaints from one of the users on that machine. Basically the user was able to send e-mails to outside world. He can also send messages and receive within his domain. But he does not receive any message from external network.
I have checked the mail logs and seen that without any errors, the messages received from external world were "removed" from the queue.
Any ideas on how this would have evolved? All of the services are in operational status.