A part from the obvious basics (IP reverse lookup working, TLS support, SMTP auth for your users..) you can also set up DKIM [1] and SPF [2] that help a lot and are well supported by big providers like gmail.
But more importantly not ending up in a blacklist is important, so if you have users using your service you should monitor the volume of outgoing emails to avoid someone using your server to spam.
There are a few tools that you can use to check your SMTP server MXToolbox and CheckTLS are the two I often use. [3]
I agree though that managing an SMTP server is challenging, I had a couple of issues I had to work on that I am sure would never have happened to a big provider.
[3] http://mxtoolbox.com http://www.checktls.com/testreceiver.html