@Tom Wrigglesworth, Thanks for posting in Q&A. From your description, it seems the devices enable Windows Hello For Business which do device register before the PDC replace have issue to verify the credentials. For the new deployment for WHFB, it is working well. If there's any misunderstanding, feel free to let us know.
After reviewing "How Windows Hello for Business works" document, I find it has a process "Key synchronization‘" which will synchronize the key from Microsoft Entra ID to Active Directory and store user's public key under the user object. It can be that the information is missing for these devices on the user object. So the verify is failed.
We can disable WHFB for the user on these devices and re-enable it to generate new information for this to make it work.
Hope the above information can help.
If the answer is helpful, please click "Accept Answer" and kindly upvote it. If you have extra questions about this answer, please click "Comment".
Note: Please follow the steps in our documentation to enable e-mail notifications if you want to receive the related email notification for this thread.