An alternate to disabling sudo completely could be as cyzczy suggested removing execute for "other" users, the commands cyzczy suggested didn't work as is so I've come up with the below:
chown root:wheel /usr/bin/sudo
chmod 4110 /usr/bin/sudo
The chown command changes the group of sudo to wheel, and the chmod command removes execute for "other" users but retains setuid and execute for owner and group, the result is root and users in the wheel group can use sudo, other users get permission denied.
[user@centos6_test ~]$ sudo sh -c 'chown root:wheel /usr/bin/sudo && chmod 4110 /usr/bin/sudo'
[user@centos6_test ~]$ sudo su - test_user
[test_user@centos6_test ~]$ sudoedit -s \\
-bash: /usr/bin/sudoedit: Permission denied
Warning, run these command as root and test in another session, and be sure you know the root password so you can us "su -" incase you break sudo.