Thanks to Johan Kiviniemi, the last upload of the command-not-found package in Feisty added support for zsh:

lionel@ouessant ~ % echo $ZSH_VERSION
4.3.2
lionel@ouessant ~ % mutt
zsh: command not found: mutt
The program 'mutt' is currently not installed.  You can install it by typing:
sudo apt-get install mutt

My colleagues are going to be happy now!