I'm doing internet servers for like 30 years now. The last three years I went back into operations and working with all the new infrastructure wonders. Feels really great. From time to time I am doing work on our mailserver that is used as a relay for customer machines. The mail queue is always a place to have a look at for things going wrong with mails.
When checking on some of the destination domains that are currently not reachable, I see a lot of domains that have no MX records set at all. My knowledge is: if you want to be reliably reachable by mail add at least two MX records of mail servers that will be able to receive mail for that domain. One master and one fall back machine. Having no MX record at all the mail server will fall back to retrieving the IP Adress of the destination mail server via the A record of its domain.
The domains in question are from businesses that are real no spam hosts or such.
These sites are misconfigured. Roughly 15 years ago such configuration would be a sure pointer to an IT department running on windows without a clue about the internet.
Did I miss anything important changes in mail configuration or is the mail misconfiguration just on the rise?
This hasn't changed much. Many companies try to cheap out on the expenses for proper IT support and have a random employee with some basic understanding of IT manage their stuff and those people tend to think that they did everything right once they are able to send and receive emails in a testing environment. Those people might be able to follow an online howto on how to set up exchange or some other random mail server software but they lack the basic understanding of DNS, especially when it comes to reverse DNS lookups, MX records etc.
No, you didn't miss anything. The recent times have seen many out of the box solutions for all kinds of services and easy to use colorful UIs, including email servers which encouraged many (especially smaller) companies to cheap out on spending cash for external services and/or IT support. This caused and will keep causing multiple issues.
Some of our customers sent unencrypted emails without knowing it, some wondered why their emails don't reach certain mailservers but others work just fine (caused by DNS errors like missing MX records, lack of encryption etc.).
You don't necessarily need a fallback machine for a proper configuration, especially in smaller companies, but having no MX records at all will result in a lot of problems. So yes, you got that right.