The extension of 4th amendment protections to telephone calls dates to a time when it was a direct analog connection between your phone and the other person's phone. But Google/Gmail is not just a dumb wire. It's an intermediate third party that can read your email and scan it to sell you ads.
It's true that this has always been the position of the Federal government, but that argument has always seemed pretty weak to me, and I don't accept it on principle, no matter how pervasive it's become. People don't expect their email to be read by others, especially the government, period. The reality that they are in fact doing this anyway just means citizens have to push harder to affect a change in the law.
This isn't a new fight. The government literally used the same exact argument when telephones were invented. It took years to work in protections for phone calls, I see no reason why the same can't be done for new modes of communications like email.
That is inconsistent with the wide usage of GMail, which (robotically) reads your mail to give you directed advertising. So GMail users at least cannot claim that they expect no one else to read their email as they've opted-in to having their mail read by running the service at all.
email servers generally aren't publicly accessible, rather they're only accessible to authorized (registered) users
The difference between telephone calls and email is that you generally don't have access to the things you need to listen in on a telephone call, but email you only need to have access to one of the routers that it's routed through
Complaint MTAs include: sendmail (>= 8.11), postfix (>= 2.2), MS Exchange (>= 5.5). Patches have existed for qmail to add support since 1.01, though they aren't in the main distribution for reasons that I'm sure make sense to djb.