Exchange requires reboot to create new mail box.

My Exchange server is not creating mailbox with new AD accounts. I am able to see the exhange tabs, but when i click on email address tab there are not detials, i.e., no email address details. If i check the mailbox store there is no mailbox created for that particular user. but on the exchange tasks page, it shows all the options as if the mailbox has already been created. there is no problem with exchange server except this.
The funny part here is that if i reboot the server, then the mail-box would be created instantly. I have tried updating and rebuilding recipient policy but it wudn't help. there is nothing in the event log. As a quick fix i've created a scheduled task to restart the server at 2am everyday. That is the only way to get the mailboxes. I've tried technet

Fairly sure a collegue in the office came across this same issue around 2 weeks ago. The issue was with the Recipient Update Service not actually running (it runs as a task to also create the exchange stuff).

I will drop him an e-mail to ask him what he did. (he is off till tomorrow)

I have found a Microsoft support document that highlights how to troubleshoot this if that is whats causing your issues.

support.microsoft.com/?kbid=822794

Also, when did it start happening ? Has any Windows updates been applied recently ? It may be worth checking if any updates have been recently installed and see if that could be a causing factor.

Cheers