How can I prevent a sudoer from editing the
This depends on how much access you have given people who use sudo. If you have given people sufficient privilege to enable them to use sudo in an unrestricted manner then you pretty much have to trust them.
You can explicitly deny access to the visudo command
however this doesn't stop people from, for example, running a shell and then running visudo
The only other solution is to reduce the scope of people's access via sudo. To do this you would have to analyse their privilege requirements and give them access via sudo to only those commands that they really need by use of command aliases etc.
Using traditional unix permissions, I think that is hard: as long as you can run any command via sudo that will allow you to do editing[*], then you're kinda screwed.
There are other security models available in Linux, though not so widely deployed and configured; for example, SELinux and AppArmour. You might be able to configure those to restrict access to what you desire.
Starting with a goal of "I want my sudo users to be able to do anything" and then taking away certain privileges is probably a hard way to do things: there are many ways to modify sudoers that don't involve directly editing (for example, replace the mail startup script with a script that i) copies over a new sudoers and then starts sendmail; reboot system; voila!)
In that sense, if you trust your users to do anything to your system, then you have to trust them to do anything to your system (on a technical level, at least).
Bit clunky, but you could set up another machine to ssh in to your box(es) and alert you if there's a change, or if it can't ssh in. Gives an attacker a small window of opportunity... but is a reduction in risk. Might not solve your particular case at all though.