Mega attachInterrupt on pins 18 or 19 require EIFR bit set first (to clear it)?
It's not that pins 18 or 19 are faulty, you are just lucky the other ones worked.

As I mention on my page about interrupts* you are recommended to always write 1 to the appropriate EIFR bit before enabling interrupts because it (the interrupt condition) may have been set in the past.

I checked the source for attachInterrupt in the file WInterrupts.c and there is no mention of the EIFR register, therefore attachInterrupt never affects that register.



* Also see my answer: How do interrupts work on the Arduino Uno and similar boards?