the first message you posted - the WARNING, message was to make sure your sender of the e-mail understood that Brightmail was trying to send the e-mail, but was having problems. This ensures that the user does not assume the mail was delivered.
The second message "exceeded max time without delivery" is telling your sender that Brightmail has given up. The e-mail was NOT delivered and the sender needs to know this.
This is normal for an e-mail system. You should NOT try to prevent these messages. They are intended to inform senders that there is something wrong with the e-mail address they used for a recipient, or, if the address is correct, that the recipients e-mail system is broken in some way.
If your sender thinks the e-mail address is correct, you should test the domain by doing an MX lookup (admin / utilities / nslookup, provide domain name and select record type = MX. This should return a list of host names or IP addresses. If it doesn't, the e-mail address is, in fact incorrect.
If you get a list of host/IP's, then the domain is valid, but perhaps the recipient name is invalid.
Look at your Brightmail scanner Delivery queues - are there any messages queued for "wrong domain"? Are there any e-mail in your message audit logs to the "wrong" domain? If not, then the original e-mail may NOT be being sent from your users, but by a spammer, using your user's
e-mail address on the spam's From:/Reply To: line.
If you see queued messages, or message audit logs outbound show activity for this domain, then your users are the source and need to fix who they are sending e-mails to.