Really? Anybody who tried contacting Google and/or Outlook.com to claim some e-mail server is legit cares to comment? Is it possible? Is it different than what the article I've liked claims:
"The standard response from all of the above boiled down to this, from Microsoft's Postmaster Troubleshooting page:
- IPs not previously used to send email typically don’t have any reputation built up in our systems. As a result, emails from new IPs are more likely to experience deliverability issues. Once the IP has built a reputation for not sending spam, Outlook.com will typically allow for a better email delivery experience.
How to build a reputation for not sending spam when they're already flagging, bouncing, or deleting my mail was unclear."
- Have people click 'not spam' on the email in GMail/Outlook
- Have people send email from those domains to yours
And the 'hints' are pretty strong it isn't
At the same time sometimes there are some gotchas that people might not be aware (and things that the big providers have to deal with and that to them are sign of spam - this should definitely be more publicized, however they want to protect this because of the actual spam senders)
Now, if their domain previously sent mail, then now it gets from a new domain this might make warnings go off
Politely contacting those email providers might help
One small anecdote: I've had Gmail flag (legitimate) mail from 'google.com' not only as Spam but as Phishing as well.