Are you using flakes? AFAIK `command-not-found` does not work with them. See https://github.com/NixOS/nixpkgs/issues/171054 and https://discourse.nixos.org/t/why-isnt-there-an-official-bui...
`nix-index` is a flake-compatible alternative: https://github.com/bennofs/nix-index