Você não especificou um host nos sudoers, portanto, ele só funciona localmente, já que você o configurou agora.
Portanto, se você definir o parâmetro do host como ALL, ele funcionará em qualquer host.
De man sudoers :
The reserved word ALL is a built-in alias that always causes a match to succeed. It can be used wherever one might otherwise use a Cmnd_Alias, User_Alias, Runas_Alias, or Host_Alias.
...
By default, if the NOPASSWD tag is applied to any of the entries for a user on the current host, he or she will be able to run sudo -l without a password. Additionally, a user may only run sudo -v without a password if the NOPASSWD tag is present for all a user's entries that pertain to the current host. This behavior may be overridden via the verifypw and listpw options.
O fato adicional de que o seguinte funciona no terminal parece confirmar que o host é o motivo pelo qual você é solicitado.
$ ssh hostname
$ sudo -u user /path/script