I have read many questions like this and have not found any resolution yet.
Recently after upgrade to 10.5.1, the custom print service on one of my arcgis servers is failing.
The print service is a geoprocessing service published using Export Web Map tool and uses some custom templates.
In one server machine, it works and in another it fails. Both arcgis servers are set identical interms of security and permissions to files and folders.
so I just tried the url on the machine itself and getting a 401.2 error... authentication should be basic and windows.
just to the rest service home page it prompts for credentials.
Basically if you can't access the service that way, then print service won't be able to do that either.
Can you figure out why you are getting prompted for credentials even when your map service is public?
Pls check this video that explain how print service works in general and see whether it helps you any way.
Enabling High-Quality Printing in Web Applications - YouTube