When is a non-unitary quantum system only theoretical?
Look at John Preskill's Lecture Notes; particularly Section 3.2.

As you noted, you can do a NAND gate by using a Toffoli gate and throwing away some of the output qubits. This results in decoherence, so you no longer necessarily have a pure state of your system.

For non-unitary quantum operations, if you assume that the environment doesn't remember anything, then the most general thing you can do is a unitary operation followed by throwing away some part of the system. 

If you assume that the environment has memory, things get much more complicated. But note that here, your operations aren't consistent because the outcome of an operation will depend on what the input was the last time you performed the operation. I don't know if you want to include this class of operations. While they are important in physics, they aren't very useful for quantum computation.