I guess I should say it now, if you give me physical access to a machine, there is no way you can stop me login in as root. If I have a machine with Linux on it (and most versions of Windows) with a CD Drive of any sort I could probably get into it as root or administrator within 15 minutes. I suspect this question refers only to SSH and even then, if a user has sudo privileages you need to be extremely careful what they are, for example. Are they able to run 'sudo /bin/bash'? 'sudo su -'? and many other commands.
I guess the best answer you can ever give is to lock the machine in a big metal box that is locked with a power lead and network lead going to it (and no this isn't a joke) and remove all Sudo privs and disable root for SSH login. And even then you still got more to worry about... rootkits... it's really a question of just how hard you can make it rather then being able to block people out of root completely.