Oooo... Well, let me think...
Contexts do not have any effect upon System Events. I have 9 Contexts for my site, served by 8 OnPageNotFound Plugins. They all behave properly and fire appropriately. Unless you are doing some custom event firing, this should not be an issue.
I can certainly help with your Context Routing, as my plugins are exactly that sort of thing. I'm inclined, though, to agree given your testing.
Other Suggestions
There are other plugins that can interfere with OnPageNotFound. What other events are you firing on?
Are you using sendForward() anywhere? This can stop OnPageNotFound even if being sent to an id that does not exist.
If you have deleted pages, but not emptied your trash, this may also interfere.
