Im pretty sure its a dns issue (again) and if you type mailq, i bet all the mail you sent is in deferred state ...
If so, fix the dns issue if your box is using a dns or just take it out on /etc/nsswitch.conf (remove dns on the hosts entry) and you would want to check also if your mail gateway is set correctly in mail.cf (DS macro on sendmail system)
A default Solaris syslog.conf configuration will log mail.debug (and above) to /var/log/syslog - not /var/adm/messages. Only mail.crit (and above) will be logged to /var/adm/messages.
Are you sure that local delivery should be disabled, and "relay=none" ? Double check those settings at your mail server config.
Also, grep -r for "916CCBA20" - this is the message ID containing the reason for the "bounceback" (at least according to your logs)
There's a useful article for relay function for sendmail, take a look here.
Ahh, this is postfix.... ok, the same applies, but you may want to see those pages to get more clarity on what's happening.
Also, there are many threads in this forum discussing mail troubleshooting, use the search function.