The UPS at my remote site went down taking down all servers. After bringing up the DC first and then Exchange, Exchange was giving event id 2601, 2604, 2501 every 15 minutes.
I ran NLTest /DSGetSite from Powershell (you can use command prompt as well) and it gave the following: Default-First-Site-Name. This is correct so why is Exchange complaining. I restarted the Exchange Active Directory service which in turn restarts all the Exchange Services but this did not stop the 3 errors being logged.
I checked MS site and found the article below where you add a new Registry key, i added the key and rebooted my Exchange Server. After the reboot no errors were reported again and Exchange was running perfectly.
One thing I did notice was before the change that the Exchange Edge Service did not start automatically, I had to manually go and start it but once the work around was in place the Service started without any errors.
Article for the adding the Registry Key:
http://support.microsoft.com/kb/2025528