I just purchased an HP LaserJet 1300, and it does indeed use/support Rendezvous (at least it shows up under Print Center's "Rendezvous" section when connected to my AirPort Base Station). Dunno about the "work flawlessly between windows- and Mac-machines" part, as I am Windows-less. I would assume that with the right amount of research, this should work fine cross-platform.
The RAM is upgradeable too which is nice, although I just learned that it takes a 100-pin DIMM and not 168-pin, which all of my spare RAM is.
-Jeremy