This probably isn't the answer your looking for, but your mention of Singapore and then reading the conversation thread at Ellis Lab, my first thought was you're hitting some internet restriction, either by the ISP, but more likely by the country.
In Singapore the government via the Media Development Authority (MDA) bans, blocks, and otherwise monitors access to any website. It's possibly random, in that one ExpressionEngine site got banned for objectionable content— anything from humor to art to politics to religion or sexuality, and they created a profile ban that hits almost all ExpressionEngine sites.
It sounds like you guys have gone through a number of test with your clients, but I recommend one more: test with a VPN in place.
We deal with a client that travels back and forth to China and we've set them up with PandaPow. This has worked well, so far. Now, I can't say if PandaPow will work well for Singapore, but they do work hard to keep there servers off of various banned list, so they may.
You should also look at this article called: Best VPN for Singapore at Start VPN. We've never tried any of the VPNs listed in the article, but the focus is directly on avoiding Singapore restrictions (which can be hard, since they don't publish them and frequently deny that they are in place).
Start with a simple test. With PandaPow you can have one of your client's download the software, pay for a single month's membership, install the software, test to see if VPN is working, then test logging in to the Control Panel. They can try using a US or Europe based IP server.
If this works, then you know it's the ban that's effecting access and can decide to proceed from there.
You can also try other options as well, if you don't want to test the VPN immediately. I'd look at:
Change Control Panel Access from
system folder to renamed
admin.php file. The idea here is that if the MDA is blocking they maybe blocking one access protocol, but not another.
Check Blacklist make sure there aren't in bans on Singapore IP addresses or generic domains, like Singtel servers. Make sure you check
.htaccess as well. It sounds crazy, but we once discovered a ban that blocked most of Russia (which we were fine with, except for 2 addresses, that we needed to have access).
I think the VPN is probably the top method, but I'd look at changing from
system folder access to renamed
admin.php access to the control panel as well, if you haven't yet.