UNIX for Advanced & Expert Users

I have a printer in another state that is setup as follows:

lj8100 printer connected to their printserver (a w2k box);
users connect to a unix app on our Sun server via Exceed (we are two states away via WAN);
users submit print jobs through an established print queue through the unix app to print to a specific printer (in this case, the lj8100 in their state;
job prints...no problem.

Here's the BUT:

They had a problem on their side with the w2k printserver, but reboot/reset the printserver. Any new jobs submitted get printed, BUT any jobs that were waiting in the print queue prior to the reboot/reset are stalled. Obviously, on our side the lpsched is running, I can do a "lpstat -o printername" and see the stalled jobs. I can send a test file to the printer from my unix workstation and the user tells me that it has printed.
Short of doing a lpshut/lpstart (this would stop the print services to hundreds of printers on this server), what can I do?

I've also tried "lp -i printer-job_# -d printername -H immediate" and "lp -i printer-job_# -d printername -H resume", but get the error message "Destination printername is unknown to the LP print service".

Am I missing anything?

Thanks in advance