Ubuntuの command not found の処理は /etc/bash.bashrc の下のほうにハンドラが書かれていて、 /usr/lib/command-not-found を実行してメッセージ出しているっぽい