So, it appears to be service account related, specifically, when we use a Microsoft managed service account, then we see the error. If we revert back to using our original windows service account (Domain account), it works properly. The solution: we had to add the managed service account to the print servers, in addition to previously having added it to the app servers
We also found that the print drivers were not automatically downloading on the app servers, which spool the print jobs to the print servers, which became evident after the error above was fixed. I loaded our Ricoh Universal print drivers on all of our app servers.
Once both steps above were done, our print jobs were spooling correctly again, with no more Printing Exceptions.