I was going to suggest
sudo until three lines from the bottom of your post...
The
setuid bit means the effective user id is taken from the
owner of the file. You should verify that the owner of these files is indeed
root, and not
bin or some other user.
I was always a little fuzzy on the particulars of setuid because it varies slightly on different unixes. I seem to recall reading that on Linux setuid does nothing if the file is a script (as opposed to a binary). On most distros I think these files are regular binaries, but I could imagine some customised distro replacing them with a script... Check they are actually binaries.
One other thing to check... that the filesystem where /sbin is stored doesn't have the nosuid mount flag set, or one of the other mount options which implies it.
If you're sure the programs are running as root, I'm not sure what is going on.