Seems you have done all I would have suggested, EXCEPT, contacting his internet provider. It is possible that THEY are using a proxy server.
A proxy server is a server that sits between your web browsers, and a real server (your internet provider). It intercepts all requests to the real server to see if it can fulfill the requests itself. If not, it forwards the request to the real server. Using proxy servers can really speed things up for the ISP. Most of the major online services such as AOL, Yahoo and MSN all use a large number of proxy servers. Providers will use proxy servers because it will speed things up dramatically in some cases.

Cookie transmission will not occur if the browsers are not set up correctly to use proxy servers. There ARE specific settings that you must use.
So, regardless of how your browser is set as far as accepting cookies, cookies won't be sent or received by your browser if proxy set up is not enabled and configured correctly. Since the cookies aren't making it through to your browser, the Web Site will assume you personally aren't accepting them.

I would check with his internet provider for correct settings. It may very well be that setting have changed since he first set up his connections.