Correct use of SMTP "Sender" header?

You're looking at the wrong things. Those are the message headers. You should be looking at the SMTP envelope. (How the envelope is specified depends from how, exactly, your application is submitting mail to the mail system. On many systems the envelope is specified by command-line arguments to the mail submission utility program.) Depending from exactly when in the protocol transaction it decides to issue that 571 response, the SMTP Relay server may not have even seen the message headers at all.

The response text is saying that the administrator of that particular SMTP Relay server you are talking to has restricted what you can put in the SMTP envelope. It appears to be complaining about the recipient part of the envelope. But it may be deferring validation of the envelope sender until specification of the first recipient, so it may be complaining about the sender.

Note that the envelope sender is where delivery status messages are sent, and you'll not want to have those directed to random people around the world. (Aside from the fact that many people don't like this, it makes no sense for delivery status messages for your mail to be returned to anyone but you.) Specify yourself as the envelope sender.

It is wrong to require MX resource records, by the way. An SMTP Relay server can be located by A and AAAA resource records in the absence of any MX resource records. See RFC 5321 § 5.1.

I might be wrong, but the most likely cause of the above error, especially in the case of Postini, is that the domains where you are getting rejected have a strict SPF policy. Most mail servers with SPF checking will be checking just the From: header, they won't care about the Sender header.

To check if this is the case run "dig +short TXT domain.com" where domain.com is what's giving you the error message. You should get back something like:

"v=spf1 mx -all"

The important part is the -all. This means that the domain owner has stated that they'll only ever send email from the servers that act as their mail servers, all other mail will be rejected.

Fortunately, if this is the case, you can actively check before sending out the email! Get the WebApp to do a SPF check when the user puts in their email address. If there is a strict policy in place, add the domain to your list. There's no shortage of libraries for all languages that can do SPF checks.