The problem is that even if the mail server initially accepts the message, it may later reject it and send a bounce. qmail, for example, does this by default for all messages.

One solution is to use VERPs, which let you track exactly what messages bounced. You can then write a handler for those bounced messages, which will do the right thing, and continue using your regular mailer to send. I think if you search for VERP you'll find some examples of how you might approach it in Perl.