Check Point supports GRE NAT only for PPP (see sk60793 - Configuring Security Gateways to allow connection to PPTP server while using Hide-NAT (GRE and Hide-NAT support)
If this is not PPP type, for example:
The Security gateway will only do NAT for GRE in the first packet. If there is another connection with the same NAT, the gateway will try to see if there is already a link for the back connection. (If there is a link, the packet is dropped.)
In R80.20, there was a problem with GRE because the NAT rulebase was run twice (unlike in older versions).
On the first run, the link was not found, and then the link for the back connection was created.
On the second run, a link was found, and consequently, the packet was dropped.