Messages awaiting directory lookup – Queue Build up on Exchange

We had an Exchange 2003 server that had a queue build up. The messages were building up in the “Messages awaiting directory lookup” queue.

After investigation we found that the server had old DNS entries which were removed and new entries were added. The queue cleared almost immediately.

If you see build up in the Messages awaiting directory lookup queue then be sure to check DNS is working as expected.