Remember that in NT-derived operating systems (W2K, WXP, Vista, 7, etc), there are per-user printer "connections" as well as per-machine "connections". Either one could be at play, and the registries of users who aren't logged-on aren't going to be available for your remote inspection.
Walking thru the registry of remote machines looking for "Local Port" references to the SMB share names of printers on the retiring print server is one possibility. If it was accessible with other protocols besides SMB (say you'd installed "Print Services for Unix" and exposed it as an LPR queue, too) you'd need to look for any other potential methods that per-machine "connections" could've been made.
I suppose you could write something to walk thru each user's printer list on logon looking for "connections" to the retiring print server. You won't know when every user has logged-on, though, unless you also plumb out some kind of reporting mechanism. If you don't have roaming user profiles and users move between computers you'll really need to inspect their registry on each computer they use. More fun.
I think you're fighting a losing battle re: trying to handle this "behind the scenes". Where I've "managed" the users' printer connections using scripts, GPOs, etc, from "day 1", I've had good success migrating print servers. OTOH, where users have been in control, I'm more apt to send out an email saying "Print server xxx is going down permanently on yyy at zzz. The new print queues are published in AD now and I'd recommend connecting to them." and just letting the chips fall where they may.
Increasingly, I'm of the opinion that users should be treated like "adults" with respect to printer selection, and so long as a good convention of identifying printer physical locations is in place on the server side, users can use the built-in tools in Windows to locate published printers and "connect" to them.
If it were me, I'd take the server offline, but leave it in a capacity that makes it easy to bring back up (say, stop the "Server" and "Print Spooler" services, or modifying the ACLs on the queues to prevent general use). Wait for complaints, resolve them when they come in (obviously, bringing the server back up to production capacity if its necessary to give you time to alleviate the short-term complaint), and then bring the server down again when you've "put out the fire". Continue until you're reasonably satisfied that you've eliminated all the "connections".