Note that bash is resolving dnf to /usr/bin/dnf. The only way I can explain that would be if the shell had cached the PATH lookup (hash), and then the file was removed.
Thanks for you feedbask. Below the outputs for asked commands:
$ uname -a Linux localhost.localdomain 6.11.6-200.fc40.x86_64 #1 SMP PREEMPT_DYNAMIC Fri Nov 1 16:09:34 UTC 2024 x86_64 GNU/Linux $ type -P dnf dnf4 dnf5 rpm-ostree~ /usr/bin/dnf /usr/bin/dnf5 $ rpm -V dnf package dnf is not installed