I think that this bug (probably as well as #813331 and #706731) could be resolved if zsh_command_not_found defined a command_not_found_handler (a built-in zsh feature) instead of a preexec hack. That would make zsh provide the actual command instead of an entire line that has to be manually lexed.
command_not_found_handler is actually pretty old, available since zsh 4.3.5 or earlier. There shouldn't be any compatibility problems. command-not-found 0.3 in Ubuntu already does this. It's probably a good idea to upgrade. Note that for this bug to be fixed, a configuration file (/etc/zsh_command_not_found) would have to be replaced.
