I've been struggling all day to get my iBook printing to a HP LaserJet 4V or a 5L that is sitting on a NT4 server. I've been using them with macs with OS8.6 and up with no problems, but I just get a load of postscript crap through from OSX.
I've been using an HP 4MV (4V + Postscript) with OS X (10.0.4) with no trouble at all--but not on an NT4 server, which is one of the reasons that I didn't reply to your note. (Another is that you say you're using a 4V; I take it from that remark that you're using the straight 4V, without Postscript, and not the 4MV.) You're not necessarily flogging a dead horse--just a horse that's missing one leg!