Unable to process group policy objects—gpsvc log shows many "deferring search" entries

A few weeks ago, we recently undertook the following operations (in a single day):

1. Commission two new Win2019 DCs in existing domain containing three Win2012R2 DCs
2. Decommission old Win2012R2 DCs
3. Raise domain and forest functional levels to Windows Server 2016

Since then, no member servers or workstations have been able to apply GPOs properly. The last process time for all GPO components (GP Environment, GP Local Users and Groups, GP Registry, etc) except for GP Infrastructure, show the last process time to be the date that we performed the above steps. The GP Infrastructure component has a proper last process time of whenever we run gpresult or RSOP.

We've enabled group policy debugging and analysed the log but there is nothing immediately obvious apart from the fact that there are a whole bunch of GPOs for which gpsvc is "Deferring search for <LDAP://cn={UID},cn=policies,cn=system,DC=example,DC=COM>". This seems to appear whenever GPO processing fails.

I can confirm there is no connectivity issues, DNS issues, FRS issues or replication issues.

What we have found is that if we remove a computer from the domain and rejoin it, everything works! It's not feasible however, to repeat this process across the organisation as there are several hundred domain-joined computers.

I cannot find any information on what "deferring search" means but I have a hunch that it may lead us to the root cause.