Given the information we learned in the comments, it appears that:

1. you ran some command with sudo (perhaps to edit sudoers to add the quoted NOPASSWD line in the Q)
2. sudo cached those credentials, allowing you to run a reboot or shutdown within timestamp_timeout (5 minutes by default, I believe)
3. but after the reboot (more than timestamp_timeout), you were again prompted for a password for those commands because there was a pre-existing ALL:ALL sudo rule without the NOPASSWD flag -- that you didn't add but were caught up in. Because sudo uses the last matching rule, it prompted you unexpectedly.

The solution here is to move your rule below the pre-existing ALL:ALL rule (or, if you like, add the NOPASSWD flag to the existing ALL:ALL rule).

Given the information we learned in the comments, it appears that:

1. you ran some command with sudo (perhaps to edit sudoers to add the quoted NOPASSWD line in the Q)
2. sudo cached those credentials, allowing you to run a reboot or shutdown within timestamp_timeout (5 minutes by default, I believe)
3. but after the reboot (more than timestamp_timeout), you were again prompted for a password for those commands because there was a pre-existing ALL:ALL sudo rule without the NOPASSWD flag -- that you didn't add but were caught up in. Because sudo uses the last matching rule, it prompted you unexpectedly.

The solution here is to move your rule below the pre-existing ALL:ALL rule (or, if you like, add the NOPASSWD flag to the existing ALL:ALL rule).

Given the information we learned in the comments, it appears that:

1. you ran some command with sudo (perhaps to edit sudoers to add the quoted NOPASSWD line in the Q)
2. sudo cached those credentials, allowing you to run a reboot or shutdown within timestamp_timeout (5 minutes by default, I believe)
3. but after the reboot (more than timestamp_timeout), you were again prompted for a password for those commands because there was a pre-existing ALL:ALL sudo rule that you didn't add but were caught up in. Because sudo uses the last matching rule, it prompted you unexpectedly.

The solution here is to move your rule below the pre-existing ALL:ALL rule (or, if you like add the NOPASSWD flag to the existing ALL:ALL rule).

Given the information we learned in the comments, it appears that:

1. you ran some command with sudo (perhaps to edit sudoers to add the quoted NOPASSWD line in the Q)
2. sudo cached those credentials, allowing you to run a reboot or shutdown within timestamp_timeout (5 minutes by default, I believe)
3. but after the reboot (more than timestamp_timeout), you were again prompted for a password for those commands because there was a pre-existing ALL:ALL sudo rule without the NOPASSWD flag -- that you didn't add but were caught up in. Because sudo uses the last matching rule, it prompted you unexpectedly.

The solution here is to move your rule below the pre-existing ALL:ALL rule (or, if you like, add the NOPASSWD flag to the existing ALL:ALL rule).