Exchange Server 2013 not working : cannot contact Active Directory

I'm a little befuddled by this situation.

I have an Exchange Server 2013 running on Windows Server 2012 R2.

It was working fine (I think), running CU17.

I decided to update it to CU21, as Microsoft says this will be the last quarterly patch for 2013 and will be required for all security patches going forward.

I take a VMware snapshot of the server, then proceeded with the upgrade.

The upgrade goes to 100%, and finishes with a single error (but no indication that the overall install failed). The error was something about not being able to find the server's site. I stupidly saved and copied the error to a text file on the server's desktop, so I can't paste it here.

More problematic than that, the Outlook website wasn't working, nor was the Exchange Control Panel website (both gave "server runtime errors").

So faced with this problem, I decided I'd just tackle the update again in the future when I had more time, and I rolled back to my snapshot at CU17.

Except, as you've probably guessed since I'm posting here, my previous snapshot isn't working now.

I can get all the Exchange services to start without any obvious errors, but my clients can't connect via their Outlook desktop apps.

The Outlook website is working, but when you actually try to send or receive emails - well, nothing is coming or going anywhere. I've tried restarting the transport services to no avail.

So I remembered back to that error I got when I tried to upgrade to CU20, and I started digging around in the server...

1. I verified the network connection is correctly configured, with static IP and DNS entry and is listed as a private network.
2. I can ping and connect via RDP to the server using the FQDN
3. I checked the event log and I get some clues and seemingly related problems:

Event 1015 MSExchangeDiagnostics Unable to contact the active directory. Inner Exception System.DirectoryServices.ActiveDirectory.ActiveDirectoryObjectNotFoundException: The computer is not in a site. at System.DirectoryServices.ActiveDirectory.ActiveDirectorySite.GetComputerSite() at Microsoft.Exchange.Diagnostics.Service.MachineInformationSource.PollMachineInformation Event 1025 MSExchange EdgeSync Topology load generated exception Microsoft.Exchange.Data.Directory.CannotGetSiteInfoException: Could not find information about the local site. This can be caused by incorrect configuration of subnets or sites or by replication latency. at Microsoft.Exchange.Data.Directory.NativeHelpers.GetSiteNameHookable(Boolean throwOnErrorNoSite) at Microsoft.Exchange.Data.Directory.SystemConfiguration.ADTopologyConfigurationSession.<GetLocalSite>b__7b() at Microsoft.Exchange.Data.Directory.Diagnostics.ADScenarioLog.InvokeWithAPILog[T](DateTime whenUTC, String name, Guid activityId, String implementation, String caller, Func 1 action, Func 1 getDcFunc) at Microsoft.Exchange.Data.Directory.SystemConfiguration.ADTopologyConfigurationSession.InvokeWithAPILogging[T](Func 1 action, String memberName)

4. I verified that the Exchange server is in the right subnet (and I haven't touched any network settings in years - no need)
5. I verified that the Exchange server appears in the right site in Active Directory Sites and Services

So, I'm thinking the key to all this is that somehow this Exchange Server's place in the AD got kind of screwed up. But I can't find the cause. I tried manually leaving the domain on the Exchange Server, and then rejoining the domain, but this fixed nothing.

Any ideas?