Habe jetzt die Lösung:
Der externe Pullup hat keine Verbesserung gebracht. Aber es lag auch nicht am Pullup selbst. Das Problem scheint zu sein, dass ich von dem für den INT-Eingang benutzten Port alle Bits auf Ausgang gesetzt habe, die ich nicht benötige (also alle außer der für den INT benötigten). Irgendwas schalte ich damit wohl ein. Muss nochmal schauen, was da alles dran hängt (ich benutze zur Zeit noch ein rnmega2560-Board zum Testen).

Vielen Dank für die Unterstützung.