Non-deterministic behavior of `sudo`

I've got a rather strange problem with sudo. Basically, it authenticates, but sometimes just doesn't launch the command provided. For example:

liori@marvin:~$ sudo whoami
root
liori@marvin:~$ sudo whoami
root
liori@marvin:~$ sudo whoami
liori@marvin:~$ sudo whoami
liori@marvin:~$ sudo whoami
liori@marvin:~$ 

I wrote a test case which demonstrates this problem:

liori@marvin:~$ sudo whoami; for i in `seq 100`; do echo -n ':' ; sudo whoami ; done ; echo
root
::::::::::::root
:::::root
:::::root
:::::::::::root
::::::::::root
::::::::::::::::::::::::::::::::root
:::root
::::root
::::root
:::root
:::root
::root
:root
:::::
liori@marvin:~$ 

Of course, the expected output is a series of lines, each one starting with exactly one colon character. I don't have any clue where to begin debugging this problem.

For each attempt (whether the command was actually run or not), I get an entry in syslog:

Apr 11 19:47:40 marvin systemd-logind[806]: New session c1079 of user root.
Apr 11 19:47:40 marvin systemd-logind[806]: Removed session c1079.

This is Debian SID. I started observing this behavior few days ago, after a somewhat bigger update (I update this system maybe once a month), and after moving the system from one hard disk to another (using rsync -av --del).

Any help will be appreciated.