We have a few locations that seemed to be having this issue for quite a while. We were running 1.2 on MSDE. The transactin would fail to print and was not logged as a transaction, so you could not reprint it. However there was always a charge in the EDC batch (Vital/TSYS). For us it almost always happened with debits and we suspected everything from our PIN pads to printer drivers and a million other things that made me pull my hair out...
Note: We were able to show a pretty good correlation between using serial/USB adapters on our Verifone PIN pads. That is to say, once we removed the adapters and just installed extra serial ports on the systems we had a lot fewer headaches. Apparently there are some drivers for serial/USB adapters that cause problems. That said, it didn't seem to completely resolve the issue at all locations.
We upgraded to 2.0 with SQL 2K5e and the problems have gone away as far as I have heard. I do still have occasional print jobs that fail but they can always be reprinted now and the transaction is logged and comes out of inventory.
Do let us know what version of SQL you're running at this location?
Also, if this is on one terminal try swapping out the the printer cable, I saw a reliable source mention that bad cables caused this issue for them in some instances... but it still sounds crazy to me.