what's to stop an attacker from compiling their own custom sudo binary that allows it to execute with any uid?
There's a basic misunderstanding going on here. The program does execute, it just stops when it notices it's not running as the root user. Recompiling the program to remove the check would only allow you to run the task as the user who executed sudo, not root. In other words, the check for running as root in sudo is only an error check and diagnostic, not a security feature.
The misunderstanding is that programs don't have any special ability to execute as another user, the extra privilege is a property of the file permissions on the file. Any program with the setuid bit set will execute as the owner of the file. If you were to compile your own program the file would be owned as you. While you are allowed to set the setuid bit on your own file, you aren't allowed to change file ownership without extra privileges. So setting the setuid bit would only allow others to execute your program as yourself.