So you have a network printer which works for some period of time and then it stops working on a couple computers, requires you to reinstall it, and that gets it to work on those computers but then causes problems for some of the remaining?
Have you tried removing the printer from each of the machines at the same time and then simply re-add them?
Network printers are tricky that way
One person could knock it offline if someone was able to get a print job in the print queue that gets stuck
What's the model of your printer?
There isn't anything out there that mentions a common network problem
is it the same few computers that start having problems with the printer?
If it's the same computers, I'd try seeing if there are newer drivers you could try installing of the printer