It sure looks to me that you're all misinterpreting ServerAliveCountMax. As I understand the docs, it is the number of server alive messages which can go unanswered without the connection being terminated. So in cases like we're discussing here, setting it to a high value will just ensure that a hung connection will not be detected and terminated!
Simply setting ServerAliveInterval should be sufficient to solve the problem with a firewall forgetting about the connection, and leaving ServerAliveCountMax low will allow the originating end to notice the failure and terminate if the connection fails anyway.
What you want is, 1) for the connection to stay open permanently under normal circumstances, 2) for connection failure to be detected and the originating side to exit on failure, and 3) for the ssh command to be re-issued every time it exits (how you do that is very platform dependent, the "while true" script suggested by Jawa is one way, on OS X I actually set up a launchd item).