A not too difficult compromise would be a bash completion plugin which knows when the command starts with "sudo" to complete these kinds of binaries. One could also argue that since sudo isn't the default, it can't have a strong influence on how the OS works. (I do personally wish sudo *was* the default though)