Unable to send emails to Hotmail or gmail from Workspaces

Hello,

I am experiencing a very weird issue. When I try to send an email from Outlook (Office 365 Business Premium) in Workspaces it gives me the below error message. This happens regardless of whether I use Outlook desktop client or web app.

-->The public IP is - 18.205.83.94. The Workspaces IP is - 172.16.1.60. <--

When I send the same type of email from outside Workspaces (e.g. using web app on my computer or via a generic email client on my phone) - it goes through without any issues.

So, it seems like the culprit is the AWS Public IP Address. If so, how do I solve this issue?.

Error Message Details:
XXXXXXXX@hotmail.com
Your message wasn't delivered because the recipient's email provider rejected it.

Diagnostic information for administrators:
Generating server: CY4PR2201MB1109.namprd22.prod.outlook.com
XXXXXXXX@hotmail.com
Remote Server returned '550 5.7.708 Service unavailable. Access denied, traffic not accepted from this IP. For more information please go to http://go.microsoft.com/fwlink/?LinkId=526653 AS(8561) [CY4PR2201MB1526.namprd22.prod.outlook.com]'
Original message headers:
Received: from CY4PR2201MB1109.namprd22.prod.outlook.com
(XXXXXXXXXXXXXXX) by CY4PR2201MB1109.namprd22.prod.outlook.com
(XXXXXXXXXXXXXXX) with mapi id 15.20.2581.007; Sat, 28 Dec 2019
14:02:59 +0000
MIME-Version: 1.0
Content-Type: text/plain
Date: Sat, 28 Dec 2019 14:02:59 +0000
Message-ID:
CY4PR2201MB11098BEFBE8AB41A8822FFCCA1250@CY4PR2201MB1109.namprd22.prod.outlook.com
Subject: Re: Test email

Edited by: DannyVC on Dec 28, 2019 8:01 AM