Mar 12 06:26:18 server-name nullmailer: Starting delivery: protocol: smtp host: mail.mydomain.com file: 1297459801.9713 Mar 12 06:26:18 server-name nullmailer: smtp: Failed: Connect failed
This is because of a miss configuration. By the time the server was installed a wrong smarthost was configured.
All I had to do to correct this was to edit nullmailer remotes file:
sudo vi /etc/nullmailer/remotes.