It sounds like a DNS issue or a routing problem. I have these problems rarely, but I do have them.
Usually, when I have this type of problem it is a DNS issue with my ISP or my domain name registrar that hosts my domain names. One test is to access the site via IP address. If I can access the site using the IP address and not by entering the domain name, I know there is no problem with the server. It has to be a DNS problem.
Several years ago, the web host I used had a problem with requests basically getting lost in the data center. Doing a traceroute, I discovered that pings would make it to the data center then time out. This happened not very often, maybe only one out of every 20 page requests. But it did happen and it was not the fault of my web host but the data center.
You have a savvy client? Did the client:
1) Try accessing the site via IP address (if possible)?
2) Try using a HTTP proxy like hidemyass.com?
3) Try flushing their DNS cache?
If the site can be accessed by IP address, it's a DNS issue either at the ISP or DNS host. If the site can be accessed using a HTTP proxy, it could be a ISP DNS or routing issue somewhere along the line. If the site can be accessed after flushing the DNS cache, then it's a DNS issue.
I'm sure there are other tests to try and narrow down the cause. Perhaps others can contribute some ideas.