As for a few examples:
1. Mailservers around the world have different degrees of strictness in what they accept. Some require the sender’s mailserver to have a valid and matching PTR and A/AAAA (!) DNS records. Others don’t care. Some check black lists, some don’t. Some even resolve the MX record of your sender domain, connect to it and try to start delivery of an email to ensure your address is valid.
2. By default, postfix doesn’t warn you about undeliverable messages for quite some time (a week is the default, I think). So if there is any error in your config (e.g. I changed my DNS resolver config, then didn’t restart postfix), your mails will be stuck without any notice, for a number of days.
3. If there are SSL certificates invoked, they should be valid. Some mail servers will not use TLS at all, some will fall back to plain text, others will cancel delivery if your certificate is invalid.
These are just a few examples I have encountered recently, but every time they happen I am incredibly frustrated that emails either did not reach me (usually I detect that quickly) or are not delivered (detected only after a few days).
apt-get install gmail-server
Still, shouldn't be that hard to do as long as it is your own server and you trust it; I imagine a lot of the difficulty of gmail is scaling, and even a single user with 20-50GB of mail isn't in the same league.
If you were to outsource it to a service provider:
I'd love a way to do privacy-protecting search on my mailbox, either by building/maintaining a local index, or even more amazingly, some kind of cryptographic/data structure magic: do processing once either pre-encryption or on the local device, then add it to an index, with a configurable slider for data leakage vs. search quality. Search could execute locally and remotely.
(This is to allow you to use webmail with no local persistent storage, or a new phone, to search your email on a server, without trusting the server).
Mutt is more like "everything I can come up with from the command line." Sure, I won't make my grandma use it, but I've never needed any searching capability beyond grep and co.
I download my email to the Mac mail app. That has let me find some emails that were unfindable on the web interface (even when I searched by sender email!)
Still, I do think there exist some very talented grafic designers out there that would enjoy playing around with a webmail interface. Hopefully, articles like this will increase the demand and interest in run-it-your-self webmail packages, so one would do that and not spend all focus on building more CMSes.
Then there's spam.. what a headache. Suddenly one day I realised that I have better things to do with my time and now everything goes through google servers.
As for hotmail, I strongly remember doing a telnet to hotmail servers and succeeded in sending emails while writing commands by hand on my private computer. Thus without any special headers or other magic, I could send email without any issues. It would had been interesting to hear details on why hotmail rejected your emails. Default postfix installation?
I wonder if there is a "Mail Admin Best Practices" doc floating around the web yet?
This is pretty good. :)
But to address some of those concerns.
While errors in the config can cause big problems, it's not very common for people to change it once it's installed. It's like doing changes to the kernel, Apache, or Xorg settings. Sure, things can easily be broken there but for the common case, the defaults are good once one has passed the installation wizard/guide.
In case of SSL issues between mail servers, I am rather sure that postfix only does a best-effort. Thus if your certification expires, they will fall back to plain text. However most CA's will warn you several times once it gets close to the one year mark, so it's not a very big workload to handle. If you know of an email server that will cancel delivery, please let me know as I would be very interested to hear it.
PTR is a real issue, but if you have static IP, PTR records should be rather easy to get. It is also a one time cost for the domain name. For a company network, a static IP and support is commonly included in the price. You email/call them, and they add a PTR. For private users, a VPN solution might be needed in some cases, but I'm unsure if it's that much of an requirement. Gmail seems fine in sending emails to locations without PTR, or receiving emails from servers without one. However I have not tested this fully or with other services like to Apple or Microsoft.
Reviewing the history of the mailop list  shows how frustrating it can be when a behemoth (AOL, MS, etc.) stops accepting your mail. It's bad enough when you're a sizeable mail operation; as a tiny standalone mailserver, you are not at all a priority, and it's possible you'll lose the ability to communicate with a significant fraction of the Internet's email users (regardless of how complete/correct your configuration) and with little recourse.
Buying a mail server in the cloud is the most practical option. I doubt EC2 would peek inside your VM to censor mail as Apple is doing here.
Running a mail server at home can get complicated. Other than having to manage the hardware yourself, there are limitations on residential internet connections. Not only do residential ISP often provide dynamic IP addresses, they tend to block port 25 (at least outgoing) so as to counter spambots. Some spam filter may also treat mail delivered from your home server more harshly.
Though, if you really can't trust anyone (cloud providers, SMTP relays, or the network in general) you're be better of using PGP.