(Twisting cables also isn't an option.)
Then use a shielded/screened cable...
Unplugging the wire turned the other wire into a large antenna I think, hence the triggering.
Not using twisted or screened cable will mean a lot more noise pickup, and that capacitor will be needed.
If you use two separate wires with a large gap inbetween you have a magnetic loop antenna, the worst
scenario of all (this is what happens if using the body / chassis of the equipment as the return wire).
An interrupt input will record the slightest pulse on the wire, even if it lasts for a fraction of a microsecond,
which makes the problem much more noticable.
Any mechanical switch will have bouncing too, which causes multiple interrupts, so you'll have to allow
for this too perhaps?