Thanks for the report.

Hmm, with '-D tree' we can see that -prune inserts a "[call stat] [need type]".

$ find -D tree -name 'a*' -prune -o -print 2>&1 | sed -n '/^Optimized command line/{n; s/ .est success rate [0-9.]*.//g; p}'
 ( -name a* -a [call stat] [need type] -prune  ) -o -print

In parser.c, we see that -prune adds it unless -depth is set:

  if (options.do_dir_first == false)
    our_pred->need_stat = our_pred->need_type = false;

And indeed, adding -depth doesn't yield the extra "[call stat] [need type]".

find -D tree -depth -name 'a*' -prune -o -print 2>&1 | sed -n '/^Optimized command line/{n; s/ .est success rate [0-9.]*.//g; p}'
 (  ( -depth -a -name a*  ) -a -prune  ) -o -print

The condition has been added in commit
https://git.sv.gnu.org/cgit/findutils.git/commit/?id=d62aacb1b

The question is why?  It seems that this because -prune uses S_ISDIR()
stop at the current level ... have to investigate.

(initially from https://unix.stackexchange.com/questions/638372/why-does-find-still-try-to-access-gvfs-and-even-includes-it-in-the-output-de by DJCrashdummy user there).

Reproduced with GNU find 4.8.0 and current git head (v4.8.0-5-gcaa03867) built with default options on Debian GNU/Linux testing amd64.

Reproducer:

$ mkdir testdir; cd testdir
$ touch a1 a2 b1 b2
$ sudo bindfs --no-allow-other . a1
$ ls -l
ls: cannot access 'a1': Permission denied
total 0
-????????? ? ?        ?        ?            ? a1
-rw-r--r-- 1 stephane stephane 0 Mar 10 11:53 a2
-rw-r--r-- 1 stephane stephane 0 Mar 10 11:53 b1
-rw-r--r-- 1 stephane stephane 0 Mar 10 11:53 b2
$ find . -name 'a*' -prune -o -print
.
./b1
find: ‘./a1’: Permission denied
./a1
./b2

See how "./a1" was output even though it matches "a*".

Here using bindfs as a different user as a way to have a file (a1) that is not lstat()able. The OP had the problem initially with a .gvfs directory (also a fuse FS mount point).

It can also be reproduced with -L/-follow and symlinks to inaccessible areas:

$ mkdir testdir; cd testdir
$ touch a2 b1 b2
$ ln -s /var/spool/cron/crontabs/foo a1
$ ln -s /no/such/file a3
$ ln -s a4 a4
$ ln -s a2/foo a5
$ find -L . -name 'a*' -prune -o -print
.
./b1
find: ‘./a1’: Permission denied
./a1
./b2
find: ‘./a5’: Not a directory
find: ‘./a4’: Too many levels of symbolic links

See how a1 was reported (for which stat() fails with EACCESS), but not  a3 (ENOENT), a4 (ELOOP), a5 (ENOTDIR).