flush_rewrite_rules not working on plugin deactivation, invalid URLs not showing 404

Have you tried delete_option('rewrite_rules'); on deactivate? I came across the following when investigating this problem and it did the trick for me:

Typically you register post types on init. Some time after that, you
get the deactivation action. A responsible plugin would remove its
rewrite rules by flushing. However, it can’t undo the registration, so
the flush doesn’t remove the plugin’s rewrites.

The hacky workaround I’ve used is to just delete the rewrite_rules
option on deactivation. They will be generated again when they are
needed, so the only noticeable effect is that the next site view may
take a bit longer.

Have a look at http://core.trac.wordpress.org/ticket/14761#comment:12 for a discussion on this topic.