There are lots of reasons that a XenDesktop desktop machine would appear as Not Registered in the Citrix Delivery Services Console. This particular Virtual Machine was being provisioned by Citrix Provisioning Services. As the desktops boot up, the Citrix Virtual Desktop Agent (VDA) service communicates with the Citrix Desktop Delivery Controller (DDC) and registers itself to notify the controllers that it is ready to accept user requests.
Failures in the registration typically occur due to a break in communication (no valid IP, no DHCP, no Network connection, etc.) but a lack of access to the Active Directory will also prevent a successful registration.
Pulling up the console for this particular desktop and attempting to log in presents me with the familiar domain trust issue that is common with provisioned machines. Jumping over to the Provisioning Console allowed me to recreate the Domain Object in AD for that machine.
Of course, once you change the Domain Object for a XenDesktop Machine, be sure to REASSIGN the Object to the Published Virtual Desktop in XD Delivery Console. Reboot and you should be good.