From what I understand, ns_sendmail doesn't actually use sendmail on the machine. ns_sendmail does all mail communication by connecting directly to the remote host on port 25.
What may be a good first test would be to attempt to telnet to the remote host on port 25 and see if you get a connection successfully. It's sounding like ns_sendmail isn't working out the address of buildaddr correctly (either by DNS or from /etc/hosts).
If all else fails, you might want to replace the hostname you have in your nsd.tcl/nsd.ini set as your mailhost and instead use the IP Address.
Let us know how you go.
HTH
