.NET program sending of email not working on client server only

I've originally asked this in SO but it seems this is a more appropriate place.

Basically, I have a program that sends email which works on my local machine and on our company's server. However, it's not working when deployed on the client's server.

The program cannot connect to the smtp server for some reason. Here is the exact error:

System.Net.Sockets.SocketException (0x80004005): A connection attempt failed because the connected party did not properly respond after a period of time, or established connection failed because connected host has failed to respond

I've logged the SMTP conversation when this error occurs and it's stuck at "AUTH LOGIN" then timeouts.

11/23/2021 5:00:13 PM - start to send email ...
11/23/2021 5:01:15 PM - failed to send email with the following error:
11/23/2021 5:01:15 PM - 
============================================================================
#Version: 7.8.0.1 - 2021-11-23 17:00:13:660
============================================================================
Server: smtp.gmail.com
Port: 587
ConnectType: ConnectSTARTTLS
Protocol: SMTP
AuthType: AuthAuto
UseDefaultCredentials: False
User: <Email>
Alias: 
Drafts: drafts
Password: <Password>
EHLO: False
PIPELINING: False
HeloDomain: <client.domain>
MailFrom: 
SocksProxyServer: 
SocksProxyPort: 1080
SocksProxyUser: 
SocksProxyPassword: 
ProxyProtocol: Socks5
============================================================================
[17:00:13:666:Verbose] Connecting smtp.gmail.com 587 ...
[17:00:13:774:Verbose] Connected
[17:00:14:347:S] 220 smtp.gmail.com ESMTP mu4sm722169pjb.8 - gsmtp
[17:00:14:348:C] EHLO <client.domain>
[17:00:14:566:S]
250-smtp.gmail.com at your service, [<client.ip>]
250-SIZE 35882577
250-8BITMIME
250-STARTTLS
250-ENHANCEDSTATUSCODES
250-PIPELINING
250-CHUNKING
250 SMTPUTF8
[17:00:14:568:C] STARTTLS
[17:00:14:784:S] 220 2.0.0 Ready to start TLS
[17:00:14:898:C] EHLO <client.domain>
[17:00:15:114:S]
250-smtp.gmail.com at your service, [<client.ip>]
250-SIZE 35882577
250-8BITMIME
250-AUTH LOGIN PLAIN XOAUTH2 PLAIN-CLIENTTOKEN OAUTHBEARER XOAUTH
250-ENHANCEDSTATUSCODES
250-PIPELINING
250-CHUNKING
250 SMTPUTF8
[17:00:15:118:C] AUTH LOGIN

11/23/2021 5:01:15 PM - System.Net.Sockets.SocketException (0x80004005): A connection attempt failed because the connected party did not properly respond after a period of time, or established connection failed because connected host has failed to respond

I've already attempted a lot of things and here are probably some notable ones:

1. Allowed port 587 in firewall
2. Disabled firewall
3. Disabled Windows Defender
4. Played around different TLS in SecurityProtocol
5. Tried both in smtp.gmail.com and smtp.office365.com - same issue
6. In other version of code where ServerCertificateValidationCallback was overridden to always return true. I actually found some windows event error saying The certificate received from the remote server was issued by an untrusted certificate authority. Because of this, none of the data contained in the certificate can be validated. The TLS connection request has failed. The attached data contains the server certificate.

I just don't know what else to do. It seems it's an infrastructure issue whether from the domain, certificates, network of the server (a cloud server), etc. but I want to ensure this before I involve them. Or at the very least, give them a starting point on what or where to look at.