Advice re: Clients connecting to VPN with CG-NAT

Hi all,

Looking at some firewall solutions for a client, and one of their highest priority is replacing their current solution due to the VPN being intermittent. Right now, the problem is if they have clients behind CG-NAT, the connections sometimes won't work, sometimes will. We've been told it's an issue if more than one to three users connect to the same mobile tower. This is a bit out of my purview, but a contractor basically said we need a technology that's compatible with CG-NAT clients. From my reading, I can only see for sure that this rules out PPTP due to GRE tunnels (which we're not using anyway). But, would IKE or IPSEC work etc? Or will we have to go with SSL based VPN like OpenVPN? Will this even work?

Whilst I love OpenVPN, I'd prefer to work with something that's got inbuilt support for all clients (if possible). Do any of you have firewall solutions with VPN's inbuilt that you know for sure work in this scenario? Thanks!