Problem is when a second document is being printed from the same computer after first one. Vista is still waiting for info on finishing the first job even 5 minutes after it was REALLY finished.
So your real problem is that the print server doesn't send back information that the job has been completed, not that Vista has a print queue.
I suggest looking up the definition of what a "queue" is (hint: it's FIFO). Vista is doing its job, the print server should be making information available to the print spooler regarding the state of the printed jobs.
Configure your print server.