Alright. Have you ever used a packet sniffer to generate a trace of network activity? www.wireshark.org
, download, install, start capture on Vista's NIC interface which would connect it to the printer. Repro the "several minutes" delay when trying to print. Stop and save the wireshark capture.
If you know how to analyse the capture yourself, you'd want to be checking whether an initial connection is made immediately as soon as the user tries to print, or whether there's literally nothing from Vista to the printer until the last few seconds when all of the activity takes place.
The capture may also reveal some sort of "retry" or error-handling behaviour which may help to explain what is happening at a network layer.