Intune Auto Enrollment and Hybrid AAD Join error

I'm working with a customer that has AD domain joined devices setup to Hybrid Join and Auto Enroll into Intune, but the results are very sporadic. The AAD Connect is syncing the users and devices in scope. The users have Intune licenses. The devices appear to be stuck at completing the Hybrid Join (pending), so the Intune enrollment doesn't happen (which is the goal).

There are 3 things that keep logging in the Device Management-Enterprise-Diagnostics event log:

1. Auto MDM Enroll <Dm Raise Toast Notification And Wait>* Failure (Unknown Win32 Error code: 0x8018002a)
2. "Auto MDM Enroll Get AAD Token: Device Credential (0x0), Resource <>* (https://enrollment.manage.microsoft.com/), Resource <>* 2 (NULL), Status (Unknown Win32 Error code: 0x8018002a)"
3. Auto MDM Enroll: Device Credential (0x0), Failed (Unknown Win32 Error code: 0x8018002a)

I had them run the following script to test connectivity: https://learn.microsoft.com/en-us/samples/azure-samples/testdeviceregconnectivity/testdeviceregconnectivity/

Both systems they tested completed all checks successfully (1 on-prem and 1 on VPN).

Still not completing the Intune Enrollment.

Has anyone been able to resolve a similar registration/enrollment error?

Thanks!