Aha! Found it. It's the NMI. I'm using the pin as an input for something else. As long as it happens to be high during the start-up and initialization - there's a 50/50 chance this will be the case - the subsequent operation is correct, and that input will recognize Port interrupts with no problems (PIT interrupts also).
What still surprises me, however, is that, even with an uncleared NMI, other code is still executed. When I paused the processor, it was in a loop of my code waiting for the system tick which never came, and this is after all the initialization code. The pause also sometimes stopped in the file of weak interrupts, which is how I finally realized what was going on.
Also, the Reference Manual states that "The pin the NMI signal is multiplexed on, must be configured for the NMI function to generate the non-maskable interrupt request." and I am not sure how that configuration is being achieved (in order to stop it).