Add a reporting feature for end users to see the last, lets say 50 email delivery status so they can be sure if an email was definitely delivered by the recipient. Or in their send items box include a small 'Delivered' or 'bounced' flag status next to the subject.

 

cPanel has a similar feature where you can view the delivery statuses of each email that you send.