[zokier]

I got this silly idea how to do it, I don't know if it works:

1. export your real $PATH to eg $REAL_PATH

2. clear $PATH (or set it to some dummy value)

3. Attach a wrapper script to command_not_found_handler, which would call the original command with REAL_PATH and pipes it to your filter (or colorizer or whatever).