In your position, after clearing the idea with both parties, I would set up a conference call involving you, the client's IT guy and your hosting provider's technical support staff. I would encourage the other two to discuss the details and expect them to jointly arrive at a solution or identify concrete steps to identify the cause.
OK if you cant get the client to talk to the hosting service, you'll have to get a clear understanding of the technical details of the problem.
NAT is Network Address Translation, it is a very common way of dealing with the shortage of IPV4 addresses. Before NAT, every computer in every organisation connected to the Internet had to have a globally unique IP-address. NAT is performed in a router to hide your internal addresses behind a different public addresses. That way, a business with 10,000 computers might only need one public IP-address instead of 10,000. Normally nowadays, internal addresses are chosen from a group of IPV4 addresses reserved for private use.
So my PC might have an internal address of 192.168.1.1 and your web-server might have an internal address of 192.168.1.1 as well. NAT makes it possible for these computers to talk to one another. Your public DNS for www.example.com does not give it's internal address 192.168.1.1, it gives the public IP-address of your router, let's say 1.2.3.4.
So when I type http://www.example.com into a web browser it sends a TCP packet that looks a bit like this
From=192.168.1.1:5432 To=1.2.3.4:80 Payload="GET / HTTP/1.0"
Where 5432 is a port my PC chose at random. My router changes that to
From=99.88.77.66:6789 To=1.2.3.4:80 Payload="GET / HTTP/1.0"
Where 99.88.77.66 is my router's public IPV4 address. This is Network Address Translation (NAT). 6789 is a port number it allocates (it may already be using 5432 for some other guy's connection) this is Port Address Translation (PAT). The router records this translation in memory for later recall.
Your hosting service router at 1.2.3.4 receives the packet and looks at the port number 80 to decide which internal computer to pass the packet onto. This is port forwarding. So on the hosting service LAN the packet is changed to
From=99.88.77.66:6789 To=192.168.1.1:80 Payload="GET / HTTP/1.0"
The web-server receives this. It replies to 99.88.77.66:6789. When that reply gets to my router it uses the port number in the target address 99.88.77.66:6789 to lookup the source of the original connection - my 192.168.1.1:5432. My router alters the destination address accordingly and forwards the packet into my LAN.
I cannot see how this can be going wrong. But you can see that the port numbers are vital in making it all work.