As I discussed earlier, some printers are inherently unsupported because they don't speak a normal printer language, instead using the computer's CPU to render a bitmap which is then piped to the printer at a fixed speed. In a few cases, these printers also speak something normal like PCL, but often they do not. In some (really low-end) cases, the printer doesn't even use a normal parallel connection but relies on the vendor's driver to emulate what should be hardware behaviour (most importantly flow control).
In any case, there are a few possible workarounds if you find yourself stuck with such a lemon.
There is now a Windows printer driver available (called mswinpr2) that will run a print job through Ghostscript before finally printing it. (Rather like an if filter in Unix's LPD). There is also a new Ghostscript driver which will print using Windows GDI calls. Taken all together, this should(tm) allow a Windows machine to print PostScript to a Windows-only printer through the vendor's driver.
If you get that working, you can then follow the instructions above for printing to a Windows printer over the network from Linux to let Unix (and other Windows, Mac, etc) hosts print to your lemon printer.
That said, I've never tried this since I don't have a winprinter, so your mileage may vary. All the software involved should be available from the Ghostscript home page (see the links in the Ghostscript section of this document).
Some HP printers use "Printing Performance Architecture" (marketingspeak for "we were too cheap to implement PCL"). This is supported in a roundabout way via the pbm2ppa translator written by Tim Norman. Basically, you use ghostscript to render PostScript into a bitmapped image in pbm format and then use pbm2ppa to translate this into a printer-specific ppa format bitmap ready to be dumped to the printer. This program may also come in ghostscript driver format by now.
The ppa software can be had from the ppa home page; pbm2ppa supports some models of the HP 720, 820, and 1000; read the documentation that comes with the package for more details on ppa printer support.
Most of the cheap Lexmark inkjets use a proprietary language and are therefore Winprinters. However, Henryk Paluch has written a program which can print in black and white on a Lexmark 7000. Hopefully he'll be able to figure out color and expand support to other Lexmark inkjets. See here for more info.