Strange Interrupt behaviour - any ideas why?

Robin, we're going to have to ask you for a schematic. 8)

I've been doing some work with that same sensor this week. It's not really a digital device. It needs a comparator or some kind of adjustable threshold to decide between 'detected' and 'not detected'. As the motor arm approaches the sensor, the response curve will rather directly measure the distance to the arm.

For my usage, I just ran it to an analog input and I apply the threshold in software. If you must use an interrupt, then I expect some external circuitry is necessary.

For extra complexity, have a look at how Sparkfun does the "digital" version of this sensor. It's not digital at all. It just uses a digital pin to charge and discharge a capacitor, giving a numerical output to the distance-sensed.