Hi Mr.Serje i hope things are fine and the code is hopefully getting done ,following i add my suggestions:
also created a double pulse at the interrupt pin, activate the interrupt request.
I think what here can be done is that as the interrupt is being fired by the NAND gate You can set a counter in here to note the number of times the interrupt routine is being fired and put in a debugging statements on the Serial (I debugged my code in the same way when I was working with interrupts that however came from a mechanical part that is a Reed Switch) this way the real culprit can be traced back, if and only if the debouncing may be happening.
also. Mr.Serje you told once that amplifying(if i recall it right from my memory) the keypad buttons may make then susceptible to ultra sensitivity and thus the same can result in debounce.