How can I discover Windows hosts to add a printer
I know this is not a real answer but I have been using Macs in (mostly) PC environments and I find the best way to print to it is by setting up a printer using it's IP address.

I rarely have any success printing thru a Windows print queue, and unless there is a rule that you HAVE to print thru the Windows server save yourself the hassle and just print directly.