Standard installation of sendmail-8.12+ requires to install sendmail binary as set group id. (/usr/sbin/sendmail → … → /usr/lib/sm.bin/sendmail in you case)
-rwxr-sr-x 1 root smmsp ...
In case of your softlinks chain try:
chown root:smmsp /usr/lib/sm.bin/sendmail chmod 2555 /usr/lib/sm.bin/sendmail
Recommended permissions are described in SECURITY file in sendmail distribution. On my debian the file is installed as /usr/share/doc/sendmail-doc/sendmail/SECURITY.gz by sendmail-doc package.