When we attempted to Recon the Macs again the process would fail with a message "Error enrolling computer. Could not recognize the JSS response."
We would receive the same error no matter what method we used to get the computer into inventory: local Recon, Quick-Add Package, command line enrolment, etc.
From the screen-shot it would seem that the problem had to do with the client or server's certificate. However, after renewing the JSS' certificate, double-checking that it was valid and that existing clients could communicate with the JSS we were at a loss to explain why Recon was failing.
The answer was both simple and completely crazy. It seems that if there is a non-standard character in the "Display message to User:" field in Restricted Software it causes Recon to fail with the above mentioned error.
The text of the original message: Este software no está permitido en la red corporativo
After changing "está" to "esta" we were able to Recon computers normally.
How bizarre is that?
A big thanks to Derek at Jamf support for figuring out the problem. We would have spent years hunting for a fix on our own.