Thanks to @JennyD, this appears to be the solution:
Turn on debugging on your sendmail test script so that you can get an accurate picture of what the problem is.
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.
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.