I am here putzing around on a mail server. If you right click on the server in ESM the go to properties the Mailbox management tab could be disabled or set to never run. That could be a problem. I have seen people set that to never run and an admin runs it periodically. Not efficient but so be it.

Now if you look under recpient update services and your main master browser isn't listed. The easiest thing is to power down the domain controllers then exchange and then power up the master browser, wait... power up the domain controllers.... wait then exchange. Hassle? Hell yes but it works to get it all back up. You can force change the roles but this works better. Trust me.

Now after that go back into RUS and force a database rebuild. Right click the domain controller and "rebuild" Then run mailbox management or set the Mail Box management to run Saturday at Midnight since its the weekend. Go home forget about exchange have a beer and check it on Monday.