If you are the host for the game then I think you have to give the game server rights aswell as internet rights. Also, when I've hosted a game, I had to knock the Local and Internet security levels down to medium as otherwise, the ports were in stealth mode and no-one can see/connect to your game (I dunno if I had to lower the security level of the local zone to get it to work, I just did

anyone know?).
If you're not the host then I think you need to just give the game internet rights with no server rights and security settings on high.
To change a programs rights, open ZA and click on Programs though the game won't be on the list of programs if it hasn't tried to access the internet with ZA loaded yet, and you can't put programs into the programs list manually AFAIK.
Also, I've got no experience with MSN Gaming Zone so I don't know if that changes anything. GameSpy will let you play with a firewall but not host games.
I always have ZA Pro running when playing online and have never needed to know any port numbers or anything.