Why Block Port 22 Outbound?
Solution 1:
I don't see that anyone has spelled out the specific risk with SSH port forwarding in detail.
If you are inside a firewall and have outbound SSH access to a machine on the public internet, you can SSH to that public system and in the process create a tunnel so that people on the public internet can ssh to a system inside your network, completely bypassing the firewall.
If fred is your desktop and barney is an important server at your company and wilma is public, running (on fred):
ssh -R*:9000:barney:22 wilma
and logging in will let an attacker ssh to port 9000 on wilma and talk to barney's SSH daemon.
Your firewall never sees it as an incoming connection because the data is being passed through a connection that was originally established in the outgoing direction.
It's annoying, but a completely legitimate network security policy.
Solution 2:
If they're blocking a mishmash of ports, letting some stuff through and blocking some other stuff at random (I love Paul Tomblin's sad tale of the people who block SSH and allowed Telnet) then they either have a very strange edge case for how they go about securing their network perimeter, or their security polices are, from the outside at least, apparently poorly thought out. You can't make sense of situations like that so just charge them the going rate for people who are a pain and carry on with your day.
If they're blocking ALL ports unless there's a specific business case for allowing traffic through that port, at which point its carefully managed then they're doing it because they're competent at their jobs.
When you're trying to write a secure application do you make it easy for other processes to read and write information to it as they please or do you have a few carefully documented APIs that you expect people to call and which you sanitise carefully?
Risk management - if you feel that traffic to or from your network going onto the Internet is a risk, then you look to minimise the amount of ways traffic can reach the Internet, both in terms of number of routes and number of methods. You can then monitor and filter these chosen "blessed" gateways and ports to try and ensure that the traffic traveling over them is what you expect.
This is a "default deny" firewall policy and is usually regarded as a good idea, with a couple of caveats which I'll come to. What it means is that everything is blocked unless there is a specific reason to unblock it, and the benefits of the reason outweigh the risks.
Edit: I should clarify, I'm not just talking about the risks of one protocol being allowed and another blocked, I'm talking about the potential risks to the business of information being allowed to flow into or out of the network in an uncontrolled way.
Now for the caveats, and possibly a plan to free things up:
It can be annoying when you're blocked out of something, which is the position you find yourself in with some of your clients. All too often, the people in charge of the firewall think its their job to say "No", instead of "Here are the risks, now what are the benefits, lets see what we can do".
If you speak to whoever manages network security for your clients they may be amenable to setting up something for you. If you can identify a few specific systems at their end you need access to, and/or guarantee you'll only connect from a specific IP address they may be a lot happier to create a firewall exception for SSH connections for those specific conditions than they would be to just open up connections to the whole internet. Or they may have a VPN facility you can use to tunnel through the firewall.
Solution 3:
A certain large company in Rochester NY that used to make a lot of film blocked outgoing ssh when I worked there, but allowed telnet! When I asked about it, they said that ssh was a security hole.
In other words, companies sometimes make stupid decisions, and then make up baloney excuses about security rather than admit their mistakes.