I feel absolutely stupid, and there doesn't appear to be a way to simply delete my post, but the solution to the problem was simple. In the Debug output, the problem part of my message looked like this:

Net::SMTP=GLOB(0x3d1148)>>> DATA
Net::SMTP=GLOB(0x3d1148)<<< 354 Start mail input; end with <CRLF>.<CRL
+F>
Net::SMTP=GLOB(0x3d1148)>>> From: root@domain.dom
Net::SMTP=GLOB(0x3d1148)>>> To: user@domain.dom
[download]

Looks fine, right?

Well, despite being sent in separate lines in the debug output, I neglected to put a "\n" after the address on both the From: and the To: lines, so it looked to the server like a bad From: address.

Changing this:

$smtp->datasend("From: $sender");
$smtp->datasend("To: $recipient");
[download]

to this:

$smtp->datasend("From: $sender\n");
$smtp->datasend("To: $recipient\n");
[download]

fixed the problem. I can't believe I missed that after debugging literally every other line of the script. I will now go back to the corner to resume biting myself. :(