$ which sendmail doesn't return anything.
sendmail IS NOT installed in non privileged users' PATH => you observer expected/normal result.
sendmail is expected to be executed by other programs like mail which use full/absolute path.
can not write to queue directory /var/spool/mqueue-client/ (RunAsGid=115, required=0): Permission denied
Does it work if you run this:
echo "Subject: sendmail test" | sudo sendmail /usr/sbin/sendmail -v firstname.lastname@example.org
The distinction being that you are running echo as root, but not sendmail.
Thus the message: "(RunAsGid=115, required=0): Permission denied"
The "115" is the Group Id of your user, and it is expecting "0" (which is roots)