If everything is setup correctly, there could be trust issues.
It happens that mails sent from new IPs (IPs that never sent mails) have delivery issues. For some providers it will work absolutely normal, yet for some it will finish in spam or not delivered.
In case of
Outlook.com, they're know to absolutely block mails from new IP addresses.
For them, there is article on Outlook.com Postmaster.
Especially take at look at
Are you sending email from new IPs?:
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.
Take a look at note too:
Note: don't forget to update your Junk Email Reporting Program (JMRP) account with the new IPs. To update or set up a JMRP account, click here.
For GMail spam issue, you need to wait until trust you. If users whitelist your email address, that process can be speed up.