Oh, as it turns out, the bug is there but not related to not finding find/grep.
It IS actually finding the find.exe and grep.exe correctly using the exec-path and/or (setenv "PATH" ..) hacks.
The problem was that the file was in a path with spaces in it:
C:\Users\kmodi\Desktop\_keep this folder empty\NEWS.txt
When I try using `A' in dired with above file marked and search for "Emacs", I get "No matches for: Emacs". Note the spaces in the directory name: "_keep this folder empty"
But when I copied NEWS.txt to C:\Users\kmodi\Desktop\NEWS.txt and then did the same "Emacs" search using `A' in dired, it worked!
I can recreate this bug in RHEL too!
(1) mkdir -p /tmp/some\ dir
(3) In emacs -Q, use C-x d to open dired in /tmp/some\ dir/
(4) Mark NEWS.txt using `m' key
(5) Then I do `A' and search for "Emacs" (or probably anything else too)
(6) You should get "No matches for: Emacs"
Can you please rename the bug title to "25.0.93; dired-do-find-regexp does not work when path contains spaces"?