Thanks to @JennyD, this appears to be the solution:

1. **[Turn on debugging](https://serverfault.com/a/746823/163277)** on your sendmail test script so that you can get an accurate picture of what the problem is.

2. Even if relaying through another host, some mail servers do a check back on you. Therefore, you need a valid domain in MASQUERADE_AS() in your /etc/mail/sendmail.mc file, it must be on this same server, and it must respond to a DNS query of A and MX records. That domain doesn't need to be the actual domain you want the From: to say, or even the Reply-To:, but is just the domain that the recipient mail server will check back against.

3. You'll need to read up on the MASQUERADE_DOMAIN, and then the allmasquerade, masquerade_envelope, and masquerade_entire_domain FEATUREs to see if you need them, and run several tests if you are serving mail for several domains from one host. In my case, I didn't need any of these. Now I can send mail as if it's from x.com, y.com, and z.com all from the same host, and when the AT&T mail server does a check back on what mail server sent it, it will list x.com in my case. However, when the SMS text alert message comes in, I can make it appear as if it's from x.com, y.com, and z.com.