I had this error pop up today:

UNKNOWN – Agent exited with code 255: Pseudo-terminal will not be allocated because stdin is not a terminal.

On a remote agent over SSH. Which I described here in check_mk_agent over SSH Host key verification failed

Turns out that the box in question could contact the outside world (a simple ping google.com was able to tell me that).

The problem? I had recently tighten the firewall rules on ufw

ufw allow out http
ufw allow out https
ufw allow out 53

Resolved the issue.

Thanks to TWright for the answer that pointed me in the right direction on Serverfault