I don't have Vista so I can't help with that part. It would be technically possible for me to test some of the other legs, but with limited free time it might take me a bit.

First thing I'd suggest... do you have an OS X machine, or some other machine you can set up as an lpd client to test if it works with things other than classic macos' driver? (or have you done that already? I guess you mention "sending a document" to it.) Might narrow down whether it is Windows or the macs that need to be hit with a hammer.