Email from our server tagged as junk by Hotmail Smartscreen unable to inform Hotmail that it is legitimate

Modern major mail services score spamminess based on multiple reputation factors, if available.

If the only factor is your IP and you don't mail often, this might be "the reputation of the /24 my IP is in". If you mail a lot, you might get your own reputation.

The easiest way to get reputation which "drowns out" the IP reputation of your netblock is to set up DKIM. Send your mails signed. This will establish a per-domain reputation, instead of per-IP reputation, and provides more signal to the automated scoring systems.

The more you work to help the recipients of your email figure out who you are and how trustworthy you are, the more signals they have to work with and the better a job the automated systems can do in deciding that you're legitimate, unlike whoever else bought a virtual machine in the same netblock, pumped out spam and then left, bills to hosting service unpaid and everyone else's reputation tarnished.

[some years later]: I wrote a blog post a couple of years back, walking through a lot of the steps needed to be able to more reliably send to large mail providers: https://bridge.grumpy-troll.org/2020/07/small-mailserver-bcp/

Really your question should be "how do I stop my emails being flagged as spam?"

The problem is that while every email service provider has some sort of spam filtering - nobody likes to say how its implemented in case the spammers use this information to get around the blocks. A lot of thought went into making IP and SMTP very highly fault-tolerant, so in the absence of end-to-end authentication there is no definitive way to separate spam from ham - leaving security by obscurity as the only solution.

I think its unlikely that the X-Authentication-Warning is explicitly causing the spam filter to kick in, however a very common feature in spam prevention is Bayesian filtering - and if that term occurs more often in spam than ham, then yes, it will contribute to the problem.

If you want to improve your deliverability, then do make sure you publish restrictive SPF 1.0 records, make sure you've masquerading configured on any internal MTAs, and make sure any external facing MTAs have PTR records published which include the mail domain in the IP address. It would also be a good idea to study how spamassassin works.

HTH

C.