How to deploy Microsoft Endpoint / InTune to computers that are in use already and not tied to Azure AD Accounts (Password Policy Failure)

We recently rolled out Microsoft Endpoint / InTune to our company computers. Everything works great if the first time a user logs in it is with their Azure AD credentials. We have computers that are in use already and we are running into a problem when those users add a work account (our Azure AD accounts) to enroll. The devices are enrolled ok, but they are failing our password policy:

When I try to have them reset their passwords, they don't get the "Change Password" option when pressing ctrl + alt + delete. We followed these directions: Error -2016281112 when you deploy password policy in Microsoft Intune

So, we are stuck getting these devices compliant with our policies because there doesn't seem to be anyway to update their password to remove the password error. I was hoping someone has hit this problem and can help us get past it.