The problem here is inkjet. You can get any number of impact printers that still have parallel ports. You can also buy plenty of nicer laser printers with parallel ports (I'm assuming IEEE 1284).
But inkjets are, by and large, crappy, throw-away printers. It's going to be hard to find something in that niche, and even if you do, you're going to have trouble with consumables...I can still buy loose toner and loose developer for an 18 year old laser printer, but ink cartridges for an inkjet old enough to be parallel? Maybe not.
I'd recommend getting slightly better printers. Check the PCL supported by your legacy app: that can be a headache.
@boden: Ahh, you've got a size limitation. What are the dimensions?