Sorry folks, my question must be really stupid, but...

I thought that
~ > ls -ld /var/spool/exim/input/
drwxr-x--- 2 mail mail 102400 Aug 12 04:10 /var/spool/exim/input/
meant the directory is owned by mail and mail has read write and execute permissions.

Furthermore, I thought that
~ > ls -l /usr/bin/movemail
-rwsr-xr-x 1 mail mail 76760 Aug 11 18:26 /usr/bin/movemail
meant that anyone in the mail group can execute movemail, and when doing so movemail will execute witht he permissions of mail (because of the s in "-rws").

But when I execute movemail (yes, I am in the mail group) the result is
~ > movemail /var/spool/exim/input/ INBOX
movemail: mailbox `/var/spool/exim/input/': cannot open: Permission denied

Its late (by now early) and I am soooo confused.

what is /usr/bin/movemail ? Where is it from?

movemail is from mailutils

Note that
~ > ls -l /usr/bin/movemail
-rwsr-xr-x 1 mail mail 76760 Aug 11 18:26 /usr/bin/movemail
~ > ls -ld /var/spool/exim/input/
drwxr-x--- 2 mail mail 106496 Aug 12 06:20 /var/spool/exim/input/
~ > ls -ld /var/spool/exim/
drwxr-x--- 6 mail mail 4096 Aug 11 18:18 /var/spool/exim/
~ > ls -ld /var/spool
drwxr-xr-x 6 root root 4096 Aug 10 11:20 /var/spool
~ > ls -ld /var
drwxr-xr-x 9 root root 4096 Aug 9 15:30 /var
~ > ls -ld /
drwxr-xr-x 23 root root 4096 Aug 11 10:53 /

Moreover,
strace movemail /var/spool/exim/input/ INBOX
shows eventually
access("/var/spool/exim/input", W_OK) = -1 EACCES (Permission denied)

As a sanity check, consider

#include <unistd.h>
#include <stdio.h>

main(int argc, char *argv[])
{
int e;

if (e = access("/var/spool/exim/input", W_OK))
perror(NULL);
return e;
}
/*
gcc -g -o access access.c
*/

c > strace ./access
execve("./access", ["./access"], [/* 31 vars */]) = 0
brk(0) = 0x122b000
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fd840a53000
access("/etc/ld.so.preload", R_OK) = -1 ENOENT (No such file or directory)
open("/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFREG|0644, st_size=64518, ...}) = 0
mmap(NULL, 64518, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7fd840a43000
close(3) = 0
open("/lib64/libc.so.6", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1\1\0\0\0\0\0\0\0\0\0\3\0>\0\1\0\0\0\300N\2\0\0\0\0\0"..., 832) = 832
fstat(3, {st_mode=S_IFREG|0755, st_size=1716472, ...}) = 0
mmap(NULL, 3828824, PROT_READ|PROT_EXEC, MAP_PRIVATE|MAP_DENYWRITE, 3, 0) = 0x7fd84048d000
mprotect(0x7fd84062b000, 2093056, PROT_NONE) = 0
mmap(0x7fd84082a000, 24576, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_DENYWRITE, 3, 0x19d000) = 0x7fd84082a000
mmap(0x7fd840830000, 15448, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_FIXED|MAP_ANONYMOUS, -1, 0) = 0x7fd840830000
close(3) = 0
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fd840a42000
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fd840a41000
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fd840a40000
arch_prctl(ARCH_SET_FS, 0x7fd840a41700) = 0
mprotect(0x7fd84082a000, 16384, PROT_READ) = 0
mprotect(0x600000, 4096, PROT_READ) = 0
mprotect(0x7fd840a54000, 4096, PROT_READ) = 0
munmap(0x7fd840a43000, 64518) = 0
access("/var/spool/exim/input", W_OK) = -1 EACCES (Permission denied)
dup(2) = 3
fcntl(3, F_GETFL) = 0x8002 (flags O_RDWR|O_LARGEFILE)
brk(0) = 0x122b000
brk(0x124c000) = 0x124c000
fstat(3, {st_mode=S_IFCHR|0620, st_rdev=makedev(136, 0), ...}) = 0
mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7fd840a52000
lseek(3, 0, SEEK_CUR) = -1 ESPIPE (Illegal seek)
write(3, "Permission denied\n", 18Permission denied
) = 18
close(3) = 0
munmap(0x7fd840a52000, 4096) = 0
exit_group(-1) = ?
+++ exited with 255 +++

again, note
access("/var/spool/exim/input", W_OK) = -1 EACCES (Permission denied)

But
c > ls -l access
-rwsr-x--- 1 mail mail 9309 Aug 12 06:53 access

I obviously have no clue as to how file permissions work...

It just occurred to me that the issue may be the distinction between file and directory.
Perhaps access does not apply to directories... and that is where EACCES (Permission denied) is comming from.

Actually, anyone can execute movemail (world rx) - it is setuid to the user mail.

Group doesn't even enter the question.

What system is this on? RH/CentOS family of distributions use SELinux to protect the system, and if the security label on the files does not permit the user access, then neither will movemail, even if it is running under the UID of mail.

One problem you are meeting is that strace uses ptrace to trace the program - And to protect the system security such a connection prevents the setuid from taking place. The strace would have to be run as root (see the manpage on strace)
Lets just say incomplete. You do appear to understand file permissions at the base level (these are usually referred to as "discretionary controls"). But that base level gets moderated by things like setuid/setgid, and on system supporting more advanced access controls (include ACLs, SELinux mandatory access) things can get a bit more complicated.

When a program is marked setuid, then anyone that can execute that program gains the access of the user identified as the owner of the file (see topics on "effective uid" vs "real uid"). In the case of movemail - that becomes the user "mail". This gets problematical, because ANY file the user mail has access to is now accessible by any user. Since the application takes a source and destination, that allows the user to copy ANY file owned/accessible by the user "mail".

Mandatory access controls are a moderation on the setuid/setgid by establishing security labels that work similarly to how the setuid moderate access. SELinux provides a ton of capability where the user is given a security label on login, and that label is matched against the label given the program file (via various table lookups) to identify whether access to a given file (which has another label). These labels are called mandatory because they are defined by the administrator (or used as a distribution standard) to prevent security violations.

That was why I asked about the host system being used. Not all distributions use SELinux, and some have different security models in use (such as AppArmor) that do things differently.

I'm not out of the weeds yet, but I suppose part of the answer
is for me to focus attention on files (rather than directories).
To be less cryptic, I first need to spend some quality time with strace...