Hello,
The NATted (one location only) node could be the origin of VoIP (voice and signalling) issues you have in one direction (for calls which originate on Taipei to TaiChung), the other direction is granted by the Firewall itself (because all LAN origination traffic is permitted and the stateful traffic is permitted too): if the signalling (other than the voice) is being blocked maybe you should pay attention on the way your CheckPoint R71 Firewall is configured to forward/route the incoming traffic to the HiPath HG1500 media gateway.
Another scenario: why not place both nodes behind firewalls (on, as example, DMZ Ethernet port but could be a LAN 2 port too if LAN 1 is also used for the PC Subnet) and then make (1) VPN between WANs and (2) forward routing between WAN interface and DMZ interface on each Firewall ?
Example:
System (A) HG LAN 1 port <-> Firewall DMZ (A) port <-- forwarding to/from --> WAN (A) <--- VPN ---> WAN (B) <-- forwarding to/from --> Firewall DMZ (B) port <-> System (B) HG LAN 1
and also adding (3) a rule to manage IP traffic (to/from) between LAN and DMZ on each Subnet's Firewall.
Best regards,
Kimera.
P.S.
By the way you should have a look at "A31003-H3580-M102-10-76A9 01/2011 HiPath 3000/5000 V8 Configuration Examples" Administrator Manual: on page 2-19 (LAN-LAN Routing) there is an example of a similar scenario using (and so enabling) the LAN 2 Ethernet port on both two HG1500 Media Gateways and then working on both Firewall's DMZ (or LAN 2) sides to managing routing between nodes.