Eventually I learned it was because Radix, my TLD registry, had noticed my domain on the Spamhaus Domain Blocklist. Who knows why it was added; I definitely hadn't been sending spam. Radix, being proactive, placed a 'serverHold' DNS status on my domain name, preventing it from resolving.
Luckily Spamhaus has an automated form for dealing with false positives. Eventually Radix removed the status. (Though, a week later it was back up, for no reason. Had to badger them for over a week to get the status removed again. Would not recommend them.) It's very lucky I wasn't trying to do anything with that domain like run a business, or rely on @<domainname> addresses to work.
TL;DR the problem is definitely not overstated.
Your registry could (and probably would) have put your domain on hold independently of where your MX points. Nothing short of choosing another TLD will protect you from your registry playing games with you.
That's not the kind of things I want to worry about. Most companies have business to run with problems of their own, thinking about DNS config and all the rules to be a good citizen (besides obvious spamming) sounds like headache and unneeded complexity to most companies. Not to mention backups, having to pay dedicated admins etc.
> most outside the small startup world still tend to keep their own mail server
Not sure about that:
https://www.google.com/work/search/customers/
https://products.office.com/en-us/business/office-365-custom...
That problem is so overstated it's not even funny. Your email will get sent to spam if your IP adress is blacklisted, or if you send spam. It's actually gotten harder to get blacklisted over time, as people has gotten more tolerant towards semi-spam ("newsletters" and stuff) and people are generally more conservative in blacklisting whole networks these days.
Don't misbehave. Don't be a bad net citizen. Get your net and DNS in order, and the default Debian set up of postfix will do you just fine. I do it and most of my customers over the years have done it too. Some outsource their spam filtering, a few outsource their whole email, but most outside the small startup world still tend to keep their own mail server.