I've just done some testing, and my sudo (1.7.4p6) does honour NOPASSWD in /etc/sudoers, when I sudo -su to any user. Are you sure your configuration is correct?
No, I'm not sure. I'm using Sudo version 1.7.4p5. sudo su <user> does not prompt for a password. sudo -su <user> and sudo -s -u <user> do prompt for a password.