Spooler restart required to flush network printouts from queue

I am having the most bizarre problem.
Our HP Color LaserJet 2600n has been working fine for months, but lately I have had to restart the Print Spooler in order for all network printouts to be sent to the printer. Printouts made locally on the server print without problems, but if a client attempts to print, this job clogs the queue until the spooler is restarted. Then all jobs are printed without error.

The only trace I have been able to find in the Event Log of this, are two messages in the System category that say that 1) “Document 2, Local Downlevel Document owned by SYSTEM was deleted on HP Color LaserJet 2600n” and 2) “Document 6, Test Page owned by was printed on HP Color LaserJet 2600n via port IP_192.168.10.245. Size in bytes: 210412; pages printed: 1″

The above messages are fired only _after_ the spooler service is restarted.

Before this started occurring (but not immediately; after more than a week) I successfully updated the printer firmware to the latest version. I also updated the printer driver to support Vista.

Anyone who can give me a hint? Two full days of troubleshooting, and still getting nowhere..

Thanks a lot for your time!
-K