Commmand works on the host I need to monitor (its IP is denoted as $HOSTADDRESS$ here):

[root@host ~]# /usr/local/nagios/libexec/check_ssh localhost
SSH OK - OpenSSH_4.3 (protocol 2.0)

However, on the Nagios server, it does not:

root@server:~# /usr/lib/nagios/plugins/check_ssh -H $HOSTADDRESS$
Server answer: 

I can see that the port is open:

root@server:~# /usr/lib/nagios/plugins/check_tcp -H $HOSTADDRESS$ -p 22
TCP OK - 0.123 second response time on port 22|time=0.123277s;;;0.000000;10.000000

And I can verify with telnet:

root@server:/etc/nagios3/conf.d# telnet $HOSTADDRESS$ 22
Trying $HOSTADDRESS$...
Connected to $HOSTADDRESS$.
Escape character is '^]'.

After searching the web for two hours and trying different suggestions I am out of ideas. I have several other hosts with similar setup, and they don't have this problem. I have compared the configs and they look the same (I think).

I am clearly missing something here.