sudo not working on certain commands

I have a rather weird problem with sudo on Debian 8. Users cannot execute some of commands in /etc/sudoers.d. I use Chef to distribute configurations, so all files are automatically generated.

Example:

This config works fine

root@server:~# cat /etc/sudoers.d/nginx 
# This file is managed by Chef.
# Do NOT modify this file directly.

user  ALL=(root) NOPASSWD:/usr/sbin/nginx

And this fails:

root@server:~# cat /etc/sudoers.d/update-rc.d 
# This file is managed by Chef.
# Do NOT modify this file directly.

user  ALL=(root) NOPASSWD:/usr/sbin/update-rc.d

user@www42:~$ sudo update-rc.d 
[sudo] password for user: 
Sorry, user user is not allowed to execute '/usr/sbin/update-rc.d' as root on server.

What can be wrong?

Diagnostics:

Mar  5 12:12:51 server sudo:    user : command not allowed ; TTY=pts/0 ; PWD=/home/user ; USER=root ; COMMAND=/usr/sbin/update-rc.d
Mar  5 12:14:25 www42 su[1209]: pam_unix(su:session): session closed for user user

root@server:~# sudo --version
Sudo version 1.8.10p3
Configure options: --prefix=/usr -v --with-all-insults --with-pam --with-fqdn --with-logging=syslog --with-logfac=authpriv --with-env-editor --with-editor=/usr/bin/editor --with-timeout=15 --with-password-timeout=0 --with-passprompt=[sudo] password for %p:  --disable-root-mailer --with-sendmail=/usr/sbin/sendmail --with-rundir=/var/lib/sudo --mandir=/usr/share/man --libexecdir=/usr/lib/sudo --with-sssd --with-sssd-lib=/usr/lib/x86_64-linux-gnu --with-selinux --with-linux-audit
Sudoers policy plugin version 1.8.10p3
Sudoers file grammar version 43

The problem is the dot in update-rc.d (in /etc/sudoers.d/update-rc.d); from man sudo:

The #includedir directive can be used to create a sudo.d directory that the system package manager can drop sudoers rules into as part of package installation. For example, given:

#includedir /etc/sudoers.d

sudo will read each file in /etc/sudoers.d, skipping file names that end in ~ or contain a . character to avoid causing problems with package manager or editor temporary/backup files.

Try and run sudo -ll to get a list of the commands/config applicable to your user.

If (as would seem to be the case) your update-rc.d clause doesn't show up, you might consider adjusting your chef recipes to deploy a single sudoers.d file per user, rather than several.

You might also consider if a group-related sudoers file might be warranted.

This question's answers might help: https://askubuntu.com/questions/246455/how-to-give-nopasswd-access-to-multiple-commands-via-sudoers