which is run by bash in the way I described.

In /etc/bash.bashrc:

# if the command-not-found package is installed, use it if [ -x /usr/lib/command-not-found -o -x /usr/share/command-not-found/command-not-found ]; then ... fi