Help! Domain of sender address does not resolve!

Are you trying to send email and seeing it rejected with "Domain of sender address does not resolve" or "Unresolvable RFC.5321 or RFC.5322 from domain"?

These SMTP rejections are telling you that something is missing from your DNS. Microsoft, Yahoo and others will reject email messages from domains that don't resolve in DNS; usually because they lack A records and/or MX records.

I've helped people send lots of mail over the years, guiding them to configure approximately a zillion different domains, and various smart people have various differing opinions on what DNS records are actually necessary for your email sending domain, whether or not you actually need an A record, whether or not both the visible from (RFC.5322 from) or return-path (RFC.5321 from) need to be resolvable in a certain way, etc. But instead of getting hung up on debating those opinions, or focusing explicitly on exactly what the relevant RFCs say, let's instead look at it through the lens of, what I know from experience is going to give you the greatest chance of not getting rejected at the SMTP gateway because of lack of one or more DNS records.

I think it boils down to this:

1. Any from domain needs to exist; to be registered and queryable in DNS (see RFC 5321 section 2.3.5). (Yahoo checks for this by looking for the the SOA; a specific DNS record that must exist for any published DNS zone. You might not be familiar with this type of record, perhaps never having set one up, because it's always been done for you, invisibly and automatically on the backend, via whatever platform you're using to manage DNS for your domains.)
2. Any from domain needs to have both an A and MX record. I know, the specs say that one or the other should be good enough; mostly true, but I have indeed seen mailbox providers in the wild that reject because a domain doesn't have BOTH, but only has one, usually in the case of having an MX record but no A record. (One such mailbox provider recently stopped maintaining their own mail gateways, but I suspect others exist.) This is one of those things where, in the past, people have wanted to fight about this, and prove that they're right, and that any mailbox provider blocking based on lack of an A record (when an MX exists) is wrong. They might be right. But I don't care about the fight. I just want to get the mail delivered, and this isn't a hill worth dying on.
3. You need an SPF record and you need to pass SPF checks. Microsoft being one of the most recent large mailbox providers to mandate that SPF must exist and must pass, along with DKIM and DMARC.
4. The MX record for your from domain needs to answer inbound port 25 and accept mail. Microsoft calls this out explicitly when they say that you must ensure that the P2 sender address can receive replies. Can they/do they confirm this somehow? I'm not sure and I don't care. You send mail; you need to accept mail.
5. Don't forget the subdomains. I used the word domain a lot above, but all applies to anything to the right of the @ sign in the from address: domains, subdomains, hostnames, any type of FQDNs (fully qualified domain names).

And when I say "from domain," I am referring to both the RFC.5321 from and RFC.5322 from. In the context of email sender best practices, their requirements for DNS records and email authentication settings have blurred together a bit, in this modern age of DMARC. They're used for distinct purposes in different ways, but you will find that the opinion of mailbox providers nowadays seems to be that both of these should resolve (and authenticate) correctly.