The chip is actually a mega644p so I tried all the bootoaders I could find for it.
I also tried with the internal pullups enabled and disabled, none of this made any difference.
I have tested with the same program written in plain C code, compiled directly by avr-gcc (on Linux) and the hex file comes out less than half the size of the one from the Arduino ide. For several hours testing this program performed perfectly.
For a control reference I just reloaded the bootloader and reprogrammed the chip by the ide and the problem returned immediately.
I think it's Gremlins hiding under the bench.