Linux find command is misbehaving

Searching for system-resolved service following the recent vulnerability disclosure, I came to see a very strange behavior from find command.

 root@localhost:/# find . -name "*systemd-resolved*"
./usr/share/man/man8/systemd-resolved.service.8.gz
./usr/share/man/man8/systemd-resolved.8.gz

The command returns 0 or two lines as output for the first run. But if I run the command the second time I get:

root@localhost:/# find . -name "*systemd-resolved*"
./usr/share/man/man8/systemd-resolved.service.8.gz
./usr/share/man/man8/systemd-resolved.8.gz
./lib/systemd/systemd-resolved
./lib/systemd/system/systemd-resolved.service.d
./lib/systemd/system/systemd-resolved.service

This means the first time, "find" does not actually find everything. Also this only happens one time. Running the command next times shows correct output. I checked this on some other systems with Debian 8 (jessie) installed. On those with Kernel 4.9+ this exact problem always occurs but on systems with kernel 3.16 it doesn't happen.
After system reboot all this happen again. But the behavior is the same for each individual system. That means that if testing on a specific system returns (wrongly) two lines of output for first run and correct output for second run, then first run of the command after rebooting the system again prints 2 lines. So the systems show same behavior after each reboot (according to my tests). Files details are as follows:

-rw-r--r-- 1 root root  ./usr/share/man/man8/systemd-resolved.service.8.gz
lrwxrwxrwx 1 root root  ./usr/share/man/man8/systemd-resolved.8.gz -> systemd-resolved.service.8.gz
-rwxr-xr-x 1 root root  ./lib/systemd/systemd-resolved
drwxr-xr-x 2 root root  ./lib/systemd/system/systemd-resolved.service.d
-rw-r--r-- 1 root root  ./lib/systemd/system/systemd-resolved.service

EDIT: To all those who suggest the problem maybe related to this specific case for these specific files: "system-resolved" is just as example. This happens when searching other keywords too. This is another example which gives wrong results for the first run:

root@localhost:/# find . -name "*apache*"

Not anybody here is able to check this problem on a Debian 8 with latest kernel from backport repository?

Solution 1:

The default version of findutils which is installed on Debian 8 is 4.4.2 and this is the newest version on jessie repositories. I download latest version (4.6.0) of findutils source code and built the binaries from source. Then I did same tests and "find" command showed correct output for the first run.

Then I downloaded findutils version 4.4.2 source code from gnu archive and compiled it. The same problem happened for the compiled find command. So this problem is not happening with findutils 4.6.0.

But I still don't know why some users don't get same results using findutils 4.4.2 (the default version of the utility installed on Debian), and don't know why Debian should still be released with this old version of findutils and possibly other Linux utilities and cause this problematic situation. And the last thing is that the exact technical reason of what strangely happened is still unknown which is not desirable. Because I'm not sure whether there's something worrisome in my OS environment.