networking - can telnet to a service, but not access service ports directly

We're running a variety of services on our cloud provider. Everything normally works fine, but occaisionally we end up with issues connecting to 1 host (which has our repos on it). We haven't been able to find a solution to the connectivity problem, so we completely rebuilt the host at a different cloud provider. Things had been running fine, but the same connectivity issue is starting again. I'll try to summarize clearly:

The host that is having connectivity issues is running Gitlab. We also ssh into that host a fair amount.

When we run into connectivity issues, we cannot access ssh, git, https etc. Pinging the host works fine. I can telnet to port 22, and get a response:

Connected to xyz.
Escape character is '^]'.
SSH-2.0-OpenSSH_7.6p1 Ubuntu-4ubuntu0.1

I can access any port on the host via Telnet, and I get back a response immediately. If I try to connect to the same host via ssh, I get:

ssh -v -v me@xyz
OpenSSH_7.9p1, LibreSSL 2.7.3
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: /etc/ssh/ssh_config line 48: Applying options for *
debug2: resolve_canonicalize: hostname xyz is address
debug2: ssh_connect_direct
debug1: Connecting to xyz [xyz] port 22.
debug1: connect to address xyz port 22: Operation timed out
ssh: connect to host xyz port 22: Operation timed out

If I disconnect from our local network, and connect via hotspot to the Internet, I'm able to access said host properly. This only happens to users on our corporate network.

I went down the path of checking all our local routers/firewalls, and couldn't find any issue. I then connected to the Internet from the external side of our corporate firewall, and the connectivity issues immediately started again.

I've spoken with our cloud provider (Google) and they see nothing wrong with our cloud configuration or servers. I've spoken with our Internet provider, and they can't see anything wrong either.

Anyone have any ideas?

Thanks.