Nitpick: when sending email, the sending mail server establishes a connection to the receiving server, not vice versa. The sender is responsible for looking up the domain name's MX record, choosing a hostname from those listed, initiating a connection, establishing an SMTP conversation, and negotiating protocol enhancements like SSL.
That said, I could see a change in behavior like this resulting from action on the receiver's side. Though the sending server makes the choice of how to connect, that choice can be influenced by the presentation of the MX record. I haven't specifically run into this before, but I could see this happening if, for example, the MX record advertised a host with an A record first (IPv4), and then was changed to list a host with only an AAAA record first (IPv6).
There's quite a lot of arcana in the email space that's difficult to manage without careful, deliberate effort. Sending email is harder than it should be, and a lot of that difficulty results from anti-spam or general anti-abuse efforts. If it was easy to bring a server up and begin sending with a new domain name and IP address while successfully reaching the inbox, then spammers would do exactly that. So new identities are put through the wringer to prove they're legitimate. Well-known platforms have an easier time sending email because they can relay traffic from infrastructure that the ISPs already trust; and in turn they maintain that trust by keeping abuse off their platform.
Whoa, I think you just solved the problem I've been having with my outbound e-mail for the last two months! Thanks so much!
Any good tips on this section in particular? If I'm running my own mail server, how would I get started making sure this is in order?
I also have a small script that puts a new sender on my whitelist of sender email addresses. My whitelist is 12000+ lines right now, collected over many years. Procmail sorts to mailing lists and vendor folders, and finally puts things that are not on the whitelist into a "possible spam" folder. From the five or ten items a day, it is easy to spot legitimate emails and I add those to the whitelist. The majority of spam is blocked by the combination of greylisting and DNSBL lists, as the delay of greylisting (ten minutes for me) is enough for them to make the blackhole list, if they happen to ever attempt delivery again.
I was thinking recently that I should be collecting statistics on the use of a lot of those aliases and whitelisted emails, and maybe start garbage collecting my lists.
There are various reputation reports and services that can tell you how your mail is doing in the major ISPs, but a lot of those require higher traffic than a personal or small business generates. There is one service, DMARC[1], that is free and can give you some visibility into how email from your domain is being processed. I put the txt record in my DNS, and Google, Facebook, Comcast, Yahoo, Fastmail, and a few others send me reports about email they have processed from my domain. It's not that interesting at the moment because things are working, but it might help to debug issues if your email was being rejected. At least I see a few spammers are trying to use my domain from their servers.
It is very easy to set up.
The full setup for inbound mail is - OpenBSD spamd (greylisting) -> internal postfix
Outbound is - internal postfix -> VPS postfix
Also, do you just have one server or a backup as well?
Using postfix + dovecot(imap) + thunderbird. 1 user, set to check mail every 9 minutes. Not even sure if I have IDLE on my server (unless it's on by default).
The SolusVM control panel shows 15-30 bytes/second (in+out) when it's idling. Now add how much your email weights and you got your bandwidth.
Greylisting still works amazingly well. With a long, long whitelist and greylisting plus DNSBL, I don't even bother running a spam filter, since the little bit of spam and emails from new senders ends up in its own directory as it came from a non-whitelisted sender.
Comcast finally started blocking residential mail server ports inbound a few years ago, so I had to migrate to a smarthost environment using a VPS as email server for $15/yr.[1]
Last year for a few months, Gmail was dropping everything I sent into the spam folder, even after recipients were marking it not spam. I eventually discovered the "Authentication-Results:" header that Gmail adds to every inbound message. It is under the "Show Original" dropdown menu. That showed that I "hadn't changed anything"(!) on my mail server, but suddenly Gmail was connecting to my mail server over an IPv6 interface, and I had never bothered to put the IPv6 block into the SPF record. Gmail was nice enough to explain exactly what it didn't like about those emails.
[1] http://lowendbox.com/blog/top-provider-poll-2014-q3-the-resu...