Hey there!
Sorry to hear you didn't have any luck with the tech you talked with - let's get this sorted out!
Does it only let the users print a certain amount, or is it a random number of times when this happens? Also, the prompts those users are getting, can you screenshot what the popup looks like? I'm guessing they are asked for a username and password each time they print, but I want to be sure.
When these users are getting the problem, do you see their print job being held in the print queue on the print server? It'd be interesting to see if the jobs are even reaching the server or not. Another good place to check is the App Log section in the PaperCut admin console, or the Real-time activity section on the Dashboard - these two places give a fair amount of information for things like authentication failures and descriptions on why jobs might be being held.
If all is well at this point, I wonder if the User Client they use to authenticate has stopped responding. Does it seem to be ending or freezing at all during these outages? Event viewer might have some information there when this happens next. Another thing you could try is force quitting the process and re-opening the application. While that's not a fix, it's a good way to see whether or not the clients having a bit of a moment.
Hopefully some of this helps! Happy to help further if you run into any walls
