Sounds like you have one of those little printer server boxes like I have at home. It allows a usb printer to be networked. USB/RJ45 thingie.
Mine has occasional trouble too. I just cycle the power on the little printer server, and it comes back online. No need to "reinstall" on each PC. Then I just go ahead and print my stuff.
The first thing I would do is assign a static address to the print server. Yes, I know the dhcp address tends to stay there but just make it a static.
Also, how is it you connect each XP station to the printer? Do use the \\server\printer type of path, or did you set a "standard tcp/ip" type of port at each PC??