This problem started happening after upgrading Symantec Antivirus on that server. It took me a while to figure it out it was the new anti-virus software causing the problem. So if you are planning to upgrade the anti-virus software on your Exchange server, don't forget to exclude Exchange folder out Auto-Realtime protection, especially the exchange data folder which might be sitting on the different partition.