Os arquivos gerados pela instalação são uma causa comum para essa mensagem de erro, conforme mencionado em: link
Por exemplo, /bin/nc aparece quando você instala o pacote netcat-openbsd .
Mas depois:
dpkg -S /bin/nc
obtemos dpkg-query: no path found matching pattern /bin/nc .
Isso acontece porque /bin/nc é gerado pela chamada update-alternatives no postst script que é executado após a instalação.
Funciona assim porque outra versão de /bin/nc é fornecida pelo pacote netcat-traditional .
Eu não acho que haja uma maneira geral de encontrar esses arquivos gerados. No caso específico de links simbólicos alternativos, podemos apenas seguir o link com readlink -f :
dpkg -S "$(readlink -f /bin/nc)"