Ssh – Fedora, ssh and sudo

I have to run a script remotely on several Fedora machines through ssh.
Since the script requires root priviliges, I do:

$ ssh me@remost_host "sudo touch test_sudo" #just a simple example
sudo: no tty present and no askpass program specified

The remote machines are configured in such a way that the password for sudo is never asked for.
For the above error, the most common fix is to allocate a pseudo-terminal with the -t option in ssh:

$ ssh -t me@remost_host "sudo touch test_sudo"
sudo: no tty present and no askpass program specified

Let's try to force this allocation with -t -t:

$ ssh -t -t me@remost_host "sudo touch test_sudo"
sudo: no tty present and no askpass program specified

Nope, it doesn't work.

In /etc/sudoers of course I have this line:

#Defaults    requiretty

… but I can't manually change it on tens of remote machines.

Am I missing something here? Is there an easy fix?

EDIT:

• Here is the sudoers file of a host where ssh me@host "sudo stat ." works.
• Here is the sudoers file of a host where it doesn't work.

EDIT 2:
Running tty on a host where it works:

$ ssh  me@host_ok tty
not a tty

$ ssh -t me@host_ok tty
/dev/pts/12
Connection to host_ok closed.

$ ssh -t -t me@host_ok tty
/dev/pts/12
Connection to host_ok closed.

Now on a host where it doesn't work:

$ ssh me@host_ko tty
not a tty

$ ssh -t me@host_ko tty
not a tty
Connection to host_ko closed.

$ ssh -t -t me@host_ko tty
not a tty
Connection to host_ko closed.

EDIT 3
Permissions on /dev/tty* on a machine where the above didn't work:

$ stat /dev/tty*
  File: `/dev/tty'
  Size: 0           Blocks: 0          IO Block: 4096   character special file
Device: fd02h/64770d    Inode: 17089401    Links: 1     Device type: 5,0
Access: (0666/crw-rw-rw-)  Uid: (    0/    root)   Gid: (    0/    root)
Access: 2013-12-11 11:44:01.000000000 +0000
Modify: 2013-12-11 11:44:01.000000000 +0000
Change: 2014-01-20 15:43:36.000000000 +0000

EDIT 4

Ok, so in the /var/log/ I have the following:

$ ls /var/log 
btmp  lastlog  maillog  messages  secure  spooler  sudo  tallylog  wtmp  yum.log

I tried with messages and secure, but they are empty. sudo on the other hand contains something… the only problem being it displays the same log message whether I use -t, -t -t or nothing:

Jun  4 17:38:52 : my_username : no tty present and no askpass program
    specified ; TTY=unknown ; PWD=/home/my_username ; USER=root ;
    COMMAND=/usr/bin/stat .