I've been running my own MTA for about 15 years now, so it's definitely possible without spending the majority of one's waking hours to do so.
Even when I switched mail server IPs twice over the last few years I didn't run into the issues you ran into. A large part of it depends on where you run it - if you, say, run it on your home Internet connection that's usually an immediate strike against you because of the insane number of spammers using backdoor'd PCs to do exactly that.
The only time I ran an MTA out of my home was when I was on a commercial ISP with a fixed IP address, that seemed to be good enough for most services including gmail and hotmail.
These days I run my MTA on a VPS with a reputable hosting provider and don't seem to have that many issues with outgoing mails marked as spam.
SPF and DKIM are pretty much a must these days, so that's a good starting point, as are the rest of the precautions you already too. I assume you're using your own domain, how "old" is that domain? That might also have an impact giving how many phishers and spammers register odd domains and use them for a short amount of time. I've used the same domain since about 1999 so that could make a difference.
I use postfix instead of qmail, but I've used qmail in the past. Both work well and are easier to configure than sendmail or exim IMHO. On top of that I do run amavisd/spamassassin/clamav for the incoming emails as well.
One more thing I've got set up that I didn't see in your list is that I've got TLS set up with a non-self signed certificate for both incoming and outgoing email. I suspect that this also makes a difference even if the other email server won't request a client certificate (most, if not all, won't). Certainly shows up when I send an email over to gmail.
My biggest issues these days are more with incoming email:
- You'll never get to the level of spam filtering that, say, gmail offers. To me, that's OK
- I use greylisting to weed out a lot of the spam that would normally make it through spamassassin, but unfortunately that's when you find out how many people have misconfigured servers that bounce emails when they encounter temporary failures