The real evil for this spec is the "update-alternatives" command. A common application like "vi" is not shipped by the various packages as "vi" but as "vim","nvi", etc and updated via update-alternatives to "vi" in the postinst scripts. This needs to be evaluated as well. The problem is that some packages embed the call in bash code with "update-alternative $pkg" (e.g. the emacs postinst), making it hard to automatically parse the code.
sudo mv /usr/lib/command-not-found /usr/lib/command-not-found-disabled
command_not_found_handle (See man bash)
declare -p -f command_not_found_handle
You can change which program is used by redefining the command_not_found_handle function.