Global Address List/GAL/OAB Not Updating

I've been doing enterprise IT for about 8 years and have never had to ask a question in a forum, because you lovely folks had already answered all my questions for other people. However, I'm very stuck, and even my co-workers aren't sure what's going on here.

I work for an MSP and one of my clients is running Exchange 2010 on Server 2008R2. It is a single domain running in a single forest, and there are no trusts anywhere. The domain is "contosoint.com" and the email addresses are all "@contosoext.com." It was set up by one of my predecessors many years ago, and as far as I can tell, all the settings were left at the defaults. I've never had any issues until a few weeks ago:

New users are added to AD (2008R2 functional level) and then mailboxes are created in Exchange. Everything goes well, the new users signs into Windows, launches Outlook, and the wizard starts setting up their mailbox. Then I get an error message:

"The name cannot be matched to a name in the address list."

This only seems to be affecting new users. They can access OWA, and they appear in the OWA address book. For existing users running Outlook 2013, the new users do not appear in the Global Address List nor in the "All Users" address list.

On the Exchange server, the new users appear in the "All Users" address book when running "Preview" in Edit Address List wizard (EMC > Organization Configuration > Mailbox > Address Lists > All Users)

I can run "Update-Global AddressList -Identity "Default Global Address List." Command runs successfully with no errors generated.

Users are not hidden from Exchange address lists in their mailbox properties.

Users have correct login UPN in AD, but I have tried both @contosoint and @contosoext UPNs. Existing users have a mix of both.

Users have correct "mail" attribute in ADSI Edit.

Address books do not have spaces in ADSI Edit/Microsoft Exchange System Objects.

"autodiscover.contosoext.com" resolves to Exchange server IP.

SRV records and forward lookup zones created for OWA and autodiscover.

Outlook Anywhere is enabled and I've tried both NTLM and basic authentication, as well as forcing basic authentication by manually configuring server settings in Outlook.

I've verified authentication in all IIS virtual directories except for "Exchange," which gives me an error "configuration section not allowed to be set below application." I compared this with another client's Exchange 2010 web.config file and they are identical at the line indicated in the error. All other directories have default authentication settings.

Followed this ldp.exe troubleshooter as best I could, except using ADSI Edit instead of ldp.exe. All of the attributes checked out and matched previously existing, functional user accounts.

Ran through the "Test E-mail AutoConfiguration" test on a user's Outlook that was already working. Received a lot of 0x80040113 errors which just confirm that the GAL doesn't have these new users.

I verified configuration of email/spam firewall.

I verified configuration of network firewall.

I verified read access to /OAB directory in IIS.

I verified all certificates were correct and valid.

I have tried manually configuring server settings for Outlook (2010 and 2013) both internally and externally. I just get prompted with a credential box over and over, which seems reasonable if Outlook is still checking the GAL for these users.

I feel like the most likely culprit was a Windows update gone bad, so I've removed recent updates, and that didn't do anything, so now it is fully patched.

I'm hoping someone has seen these symptoms but had a resolution outside of these troubleshooting steps. I appreciate any input!