File executable by all, yet still cannot be executed

find will set its return code to non-zero if it saw an error. So you can do:

if ! find ... 
then    echo had an error >&2
fi |
while ...

(I'm not sure what you want to do with the find output).

To collect all the error messages from find on stderr (file descriptor 2) you can redirect 2 to a file. Eg:

if ! find ... 2>/tmp/errors
then     zenity --error --text "$(</tmp/errors)"
fi |
while ...

I read through the manual page for the system function and came across the following passage which offers an explanation:

Do not use system() from a program with set-user-ID or set-group-ID
privileges, because strange values for some environment variables
might be used to subvert system integrity.  Use the exec(3) family of
functions instead, but not execlp(3) or execvp(3).  system() will
not, in fact, work properly from programs with set-user-ID or set-
group-ID privileges on systems on which /bin/sh is bash version 2,
since bash 2 drops privileges on startup.  (Debian uses a modified
bash which does not do this when invoked as sh.)

Here are some other StackExchange posts that I read through on my way to that passage:

• SETUID Permission Denied
• Why do I need setuid(0) within a setuid-root C program that calls an administrative program with system()?
• Debugging a setuid program / “Permission denied” with setuid
• Unix suid bit problem
• how to set the setuid bit in a program of a non-root user?
• linux setuid does not work

For posterity, and because the given example might be useful for diagnosing this or similar issues in other contexts, I've kept my original below.

Is it possible that you're running into a bug? I was unable to reproduce your problem in a Docker container running Debian 9 with gcc 6.3. Here is how I went about trying to recreate the scenario described in your post.

First create the "alice" and "bob" users and them to the "staff" group:

useradd -m -G staff alice
useradd -m -G staff bob

Next create the file and set its ownership and permissions:

# Create a subdirectory to hold the text file
sudo -u alice mkdir -p /home/alice/share/

# Create the text file
sudo -u alice bash -c 'echo "This is foo.txt" > /home/alice/share/foo.txt'

# Set restrictive permissions on the text file
chmod u=rw,g=,o= /home/alice/share/foo.txt

Let's check the results:

$ ls -l /home/alice/share/foo.txt
-rw------- 1 alice alice 16 Nov  4 15:33 /home/alice/share/foo.txt

Now let's create a version of display-foo which uses the system function:

$ cat <<HEREDOC > /usr/local/src/display-foo.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/types.h>
#include <pwd.h>

int main(int argc, char **argv) {

    struct passwd *r_pwd = getpwuid(getuid());
    printf("Real user: %s\n", r_pwd->pw_name);

    struct passwd *e_pwd = getpwuid(geteuid());
    printf("Effective user: %s\n", e_pwd->pw_name);

    system("/bin/cat /home/alice/share/foo.txt");
}
HEREDOC

$ gcc /usr/local/src/display-foo.c -o /usr/local/bin/display-foo

And let's set ownership and permissions on display-foo, including setting the setuid bit:

chown alice:alice /usr/local/bin/display-foo
chmod u=rwx,g=rx,o=rx /usr/local/bin/display-foo
chmod u+s /usr/local/bin/display-foo

Let's also check the result:

$ ls -l /usr/local/bin/display-foo
-rwsr-xr-x 1 alice alice 8640 Nov  4 15:40 /usr/local/bin/display-foo

Now we run the program both as alice and as bob:

$ sudo -u alice display-foo

Real user: alice
Effective user: alice
This is foo.txt

$ sudo -u bob display-foo

Real user: bob
Effective user: alice
This is foo.txt

As you can see, it looks like everything is working as expected.