There were a couple of things that we found to help (we're not entirely certain which part fixed it..)
So to explain the first one; a user had changed their language to "english - international" and his seemed to be the account that did it the most. Chanigng back to the default "english - american" made it better for him and so we disabled the personalization on the machine. Unfortunately this actually stops a user from being able to add shortcuts/apps but luckily none of ours use it.
The issue came back for a few users but less often so; we decided to do a network trace with the firewall (as the printers are communicating with a server and dns on a different vlan). This showed some random dns requests that were failing - turned out multicast dns was enabled on the printer. We disabled this and we've not seen the issue since.
So my advice is to do a network trace if you can, see if there's any failed dns requests and check the multicast dns settings.
Good luck, keep us updated!
