This is not correct. sudo only requires the user's own password.

If I understand correctly, you have configured sudo to allow these users to execute any command they want, and then separately prohibited the shell, in order to prevent them from evading the logging.

The problem is that you cannot enforce your policy if you have a "permit unless prohibited" policy. Only with "prohibit unless permitted" and by explicitly listing the commands the users are allowed to execute as admin can you meaningfully enforce your policy.

These are your options; I don't think you like the answer, but that's how it is. Either explicitly list all the permitted commands, or live with the fact that some user could come up with a workaround to evade the logging. If you trust them to run arbitrary commands, what's to prevent them from installing a remote backdoor if they wanted to? It's "turtles all the way down".