I figured it out. I had a VPC Access Connector that was all traffic for Cloud Run was passing through. Even when it was turn on an Egress Firewall rule that applied to the VPC Connector (using tags), it still didn't work. I had to reconfigure the the VPC Connector options to be "Route only requests to private IPs through the VPC connector".
Something I haven't tried is to setup a static IP address for the VPC Connector (Static outbound IP address | Cloud Run Documentation | Google Cloud). This could work