I really do not miss installing Internet at hotels every day.
The fix is simple. You need to give VPN users a 1 to 1 NAT manually. Like this...
1) They call in with issue.
2) You ask them for their IP address, and when they are leaving.
3) You add that IP address to 1 to 1 NAT with an expiry date.
4) Ask them to try again and it works.
5) Clean up all the expired addresses no one else has cleaned up.
And yeah, this takes a boatload of staic IPs to do this, and all of them have to be in proxy arp.
And yes, this could be reasonably scripted from within CP and stuff, but it would not be trivial.