"Can not write to queue directory" error and other sendmail issues after updating linode from Debian 8 to Stable

I followed this tutorial to upgrade my linode instance from Debian 8 to Stable. In the wake of that upgrade, I've had several errors/issues with sendmail.

1. $ which sendmail doesn't return anything. I do have sendmail installed. It's at /usr/sbin/sendmail.

2. Sendmail's permissions are as follows:

   $ ls -la /usr/sbin/sendmail lrwxrwxrwx 1 root root 26 Jul 17 12:41 /usr/sbin/sendmail -> /etc/alternatives/sendmail

   The link (/etc/alternatives/sendmail) is highlighted in red.

3. When I try to send a test email with sudo echo "Subject: sendmail test" | /usr/sbin/sendmail -v [email protected] I get the following error:

   can not write to queue directory /var/spool/mqueue-client/ (RunAsGid=115, required=0): Permission denied

   That directory's permissions are:

   $ ls -la /var/spool/mqueue-client drwxrwxr-x 2 root root 4096 Sep 15 2018 mqueue-client

So, I obviously have some sort of permission/ownership issue, but I also think there's something else going on given items 1 and 2. I need to be able to receive emails from the system's OSSEC and Fail2ban, so I can't really go without a working email client/server. I'm just not sure how to fix these issues.

My sendmail was simply installed with $ sudo apt-get install sendmail sendmail-bin, so it came direct from Debian's repos, which is why I'm a bit baffled by these issues... I assumed that whatever configuration was needed would be handled by the installation process.

EDIT: the output of ls -l /etc/alternatives/sendmail*

lrwxrwxrwx 1 root root 24 Jul 17 12:41 /etc/alternatives/sendmail -> /usr/lib/sm.bin/sendmail
lrwxrwxrwx 1 root root 42 Jul 17 12:41 /etc/alternatives/sendmail.8.gz -> /usr/share/man/man8/sendmail.sendmail.8.gz

lrwxrwxrwx 1 root root 24 Jul 17 12:41 /etc/alternatives/sendmail-msp -> /usr/lib/sm.bin/sendmail
lrwxrwxrwx 1 root root 42 Jul 17 12:41 /etc/alternatives/sendmail-msp.8.gz -> /usr/share/man/man8/sendmail.sendmail.8.gz

lrwxrwxrwx 1 root root 24 Jul 17 12:41 /etc/alternatives/sendmail-mta -> /usr/lib/sm.bin/sendmail
lrwxrwxrwx 1 root root 42 Jul 17 12:41 /etc/alternatives/sendmail-mta.8.gz -> /usr/share/man/man8/sendmail.sendmail.8.gz

Each pair ends in a different color, e.g. /usr/lib/sm.bin/sendmail is highlighted in amber, while /usr/share/man/man8/sendmail.sendmail.8.gz is highlighted in red. It's the same colors - amber and red - for each pair.

EDIT2: The output of (echo subject: test; echo ; echo test) | /usr/sbin/sendmail -d44.4 -i -v username (I used my real username, but have adjusted the resulting output for security):

$ (echo subject: test; echo ; echo test) | /usr/sbin/sendmail -d44.4 -i -v username
safefile(/etc/mail/submit.cf, uid=1000, gid=0, flags=6000, mode=400):
safedirpath(/etc/mail, uid=1000, gid=0, flags=6000, level=0, offset=0):
    [dir /etc/mail] OK
    [uid 0, nlink 1, stat 100644, mode 4]   OK
safefile(/etc/mail/relay-domains, uid=1000, gid=0, flags=6580, mode=400):
safedirpath(/etc/mail, uid=1000, gid=0, flags=6580, level=0, offset=0):
    [dir /etc/mail] OK
    No such file or directory
safefile(/etc/mail/service.switch, uid=1000, gid=115, flags=6480, mode=400):
safedirpath(/etc/mail, uid=1000, gid=115, flags=6580, level=0, offset=0):
    [dir /etc/mail] OK
    [uid 0, nlink 1, stat 100644, mode 4]   OK
safefile(/etc/mail/service.switch, uid=1000, gid=115, flags=6480, mode=400):
safedirpath(/etc/mail, uid=1000, gid=115, flags=6580, level=0, offset=0):
    [dir /etc/mail] OK
    [uid 0, nlink 1, stat 100644, mode 4]   OK
safefile( , uid=1000, gid=115, flags=40, mode=660):
safedirpath(., uid=1000, gid=115, flags=40, level=0, offset=0):
    [dir .] OK
    No such file or directory
    [final dir . uid 111 mode 42770] Success
safedirpath(/var/spool/mqueue-client, uid=1000, gid=115, flags=0, level=0, offset=0):
    [dir /var/spool/mqueue-client] OK
safefile(./dfx6MIGnM5005502, uid=1000, gid=115, flags=2040, mode=600):
safedirpath(., uid=1000, gid=115, flags=2040, level=0, offset=0):
    [dir .] OK
    No such file or directory
    [final dir . uid 111 mode 42770] Success
username... Connecting to [127.0.0.1] via relay...
220 major-productions.com ESMTP Sendmail 8.15.2/8.15.2/Debian-12; Mon, 22 Jul 2019 14:16:49 -0400; (No UCE/UBE) logging access from: localhost(OK)-localhost [127.0.0.1]
>>> EHLO major-productions.com
250-major-productions.com Hello localhost [127.0.0.1], pleased to meet you
250-ENHANCEDSTATUSCODES
250-PIPELINING
250-EXPN
250-VERB
250-8BITMIME
250-SIZE
250-DSN
250-ETRN
250-AUTH DIGEST-MD5 CRAM-MD5
250-DELIVERBY
250 HELP
>>> VERB
250 2.0.0 Verbose mode
>>> MAIL From:<[email protected]> SIZE=20 [email protected]
250 2.1.0 <[email protected]>... Sender ok
>>> RCPT To:<[email protected]>
>>> DATA
250 2.1.5 <[email protected]>... Recipient ok
354 Enter mail, end with "." on a line by itself
>>> .
421 4.3.0 collect: Cannot write ./dfx6MIGnHm005503 (bfcommit, uid=0, gid=115): No such file or directory
>>> QUIT
username... Deferred: 421 4.3.0 collect: Cannot write ./dfx6MIGnHm005503 (bfcommit, uid=0, gid=115): No such file or directory
safefile(/var/lib/sendmail/sm-client.st, uid=1000, gid=115, flags=2282, mode=600):
safedirpath(/var/lib/sendmail, uid=1000, gid=115, flags=2282, level=0, offset=0):
    [dir /var/lib/sendmail] OK
    No such file or directory
safefile(/var/lib/sendmail/sm-client.st, uid=1000, gid=115, flags=2282, mode=600):
safedirpath(/var/lib/sendmail, uid=1000, gid=115, flags=2282, level=0, offset=0):
    [dir /var/lib/sendmail] OK
    No such file or directory
Closing connection to [127.0.0.1]

EDIT 3: the output of (echo subject: test; echo ; echo test) | /usr/sbin/sendmail -Am -d44.4 -i -v username while logged in as root (with the username obfuscated as before):

# (echo subject: test; echo ; echo test) | /usr/sbin/sendmail -Am -d44.4 -i -v username
safefile(/etc/mail/sendmail.cf, uid=0, gid=0, flags=6000, mode=400):
safedirpath(/etc/mail, uid=0, gid=0, flags=6000, level=0, offset=0):
    [dir /etc/mail] OK
    [uid 0, nlink 1, stat 100644, mode 400]     OK
safefile(/etc/mail/local-host-names, uid=0, gid=0, flags=6580, mode=400):
safedirpath(/etc/mail, uid=0, gid=0, flags=6580, level=0, offset=0):
    [dir /etc/mail] OK
    [uid 0, nlink 1, stat 100644, mode 400]     OK
safefile(/etc/mail/relay-domains, uid=0, gid=0, flags=6580, mode=400):
safedirpath(/etc/mail, uid=0, gid=0, flags=6580, level=0, offset=0):
    [dir /etc/mail] OK
    No such file or directory
safefile(/etc/mail/service.switch, uid=0, gid=0, flags=6480, mode=400):
safedirpath(/etc/mail, uid=0, gid=0, flags=6580, level=0, offset=0):
    [dir /etc/mail] OK
    [uid 0, nlink 1, stat 100644, mode 400]     OK
safefile(/etc/mail/service.switch, uid=0, gid=0, flags=6480, mode=400):
safedirpath(/etc/mail, uid=0, gid=0, flags=6580, level=0, offset=0):
    [dir /etc/mail] OK
    [uid 0, nlink 1, stat 100644, mode 400]     OK
safedirpath(/var/spool/mqueue, uid=0, gid=0, flags=4, level=0, offset=0):
    [dir /var/spool/mqueue] OK
safefile(/etc/mail/service.switch, uid=0, gid=0, flags=6480, mode=400):
safedirpath(/etc/mail, uid=0, gid=0, flags=6580, level=0, offset=0):
    [dir /etc/mail] OK
    [uid 0, nlink 1, stat 100644, mode 400]     OK
safefile(/etc/mail/aliases.db, uid=0, gid=0, flags=584, mode=400):
safedirpath(/etc/mail, uid=0, gid=0, flags=584, level=0, offset=0):
    [dir /etc/mail] OK
    [uid 110, nlink 1, stat 100640, mode 400]   OK
safedirpath(/home/username, uid=1000, gid=1000, flags=1985, level=0, offset=0):
    [dir /home/username] OK
safefile(/home/username/.forward.major-productions, uid=1000, gid=1000, flags=1895, mode=400):
    No such file or directory
safedirpath(/home/username, uid=1000, gid=1000, flags=1985, level=0, offset=0):
    [dir /home/username] OK
safefile(/home/username/.forward, uid=1000, gid=1000, flags=1895, mode=400):
    No such file or directory
safefile(./dfx6MKLN6r006080, uid=0, gid=0, flags=2040, mode=600):
safedirpath(., uid=0, gid=0, flags=2040, level=0, offset=0):
    [dir .] OK
    No such file or directory
    [final dir . uid 0 mode 40700] Success
username... Connecting to local...
safefile(/usr/sbin/sensible-mda, uid=0, gid=0, flags=41904, mode=0):
safedirpath(/usr/sbin, uid=0, gid=0, flags=41904, level=0, offset=0):
    [dir /usr/sbin] OK
    [uid 0, nlink 1, stat 104755, mode 0]   OK
username... Sent
safefile(/var/lib/sendmail/sendmail.st, uid=0, gid=0, flags=2282, mode=600):
safedirpath(/var/lib/sendmail, uid=0, gid=0, flags=2282, level=0, offset=0):
    [dir /var/lib/sendmail] OK
    No such file or directory
safefile(/var/lib/sendmail/sendmail.st, uid=0, gid=0, flags=2282, mode=600):
safedirpath(/var/lib/sendmail, uid=0, gid=0, flags=2282, level=0, offset=0):
    [dir /var/lib/sendmail] OK
    No such file or directory

1. $ which sendmail doesn't return anything.

sendmail IS NOT installed in non privileged users' PATH => you observe expected/normal result. sendmail is expected to be executed by other programs like mail which use full/absolute path.

3. can not write to queue directory /var/spool/mqueue-client/ (RunAsGid=115, required=0): Permission denied

fix /var/spool/mqueue-client permissions and ownership

chown smmsp:smmsp /var/spool/mqueue-client`   
chmod 02770 /var/spool/mqueue-client`

MODERN SENDMAIL DOES NOT REQUIRE TO BE SET INSTALLED AS SET ROOT ID

see results of ls -l --dereference /usr/sbin/sendmail in the question's comments:
-r-sr-sr-t 1 root smmsp 860672 Sep 15 2018 /usr/sbin/sendmail

Change permission of the final target of /usr/sbin/sendmail and /etc/alternatives links in Debian:

chmod u-s /usr/lib/sm.bin/sendmail