Pues a mi me pasaba una cosa similar no ocn ese juego si no con el AOE ome dejaba crear partidas, aun abriendo los puertos (3COM 812) la solución: Te metes al router y en configuracion->remote sites profile-> modify -> Next y en default worstation pone sla IP privada en la que kieres hacer de server
Con esto hacemos que todos los puertos se mapeen solos es decir es como si el router lo ponemos en monopuesto pero en multipuesto, y si te obsesiona la seguridad, pone sun firewall y listo.
Un saludo