Try googling KYC and AML, they may help.
Surely its not a universal thing, nor an obligatory law everywhere, as most banks in eastern Europe, and many in western Europe too, do not require such a thing to open a bank account, you just tell them the address you want them to send statements to, and that's it.
Its mostly banks in UK which rigorously require such a thing as "proof of address" by a "utility bill".
If it was a AML requirement, then banks would be the first to require this, and many, if not most, don't.
Anyway anyone with two brain cells will figure out in 5 seconds that for AML purpose this is pointless, as anyone who would be up to launder some dirty money will get an "utility bill" without problems, it'll just cost him some money, maybe to rent a unneeded flat and sign up for electricity for one month, and then cancel - but for money launderers wasting a bit of money is not a problem. But it is a problem for a lot of normal people, who do not rent a place with utility bills in their name, and have to waste their time and money to get such a useless "pesudo-document".
Although FATF countries are required to implement the FATF recommendations (AML, KYC, CTF), it's an over-arching framework and individual nations decide on how they're going to implement them. Most countries specify the minimum KYC information required to open an account (it used to be 100 points of ID in Australia, which meant multiple sources of ID from different classes), but the verification requirements change according to how the account is actually used once opened. Any transactions which trigger enhanced due diligence requirements (and the bar is set low for this) will trigger increased verification requirements.
Even when it's not technically required, some institutions require full verification at the outset because it's a lot less inconvenient for customers than suddenly asking them to provide enhanced KYC information when the system flags activity on their account as "high risk". Others work on the basis that the administrative burden of taking this approach is too great and that the majority of customers will never have high risk transactions so they request verification information on an "as needed" basis (which does inconvenience customers).
Verification often requires a combination of old and new documents (many places don't accept utility bills which are more than three months old but won't accept a birth certificate which has only just been acquired). Forms of ID which themselves require you to prove your identity are often heavily favoured as are types of ID where there's a legal requirement to keep your address up to date (drivers licences in many countries).
Does all of this mean that some people won't be able to meet the verification requirements of overseas financial services? Sure it does, but they're first and foremost obliged to comply with their local regulations. They're not obliged to accept you as a customer and bending the rules to do so threatens their own interests as well as the interests of other customers.
Hell, sometimes companies decide to exclude a customer group just because including them would be a total pain in the ass. This is happening with foreign financial service providers and US customers right now because foreign companies don't want to have to deal with implementing FACTA requirements (which would require them to report the financial activity of US customers to the IRS).
Exchanges are on the razor's edge already when it comes to staying in business and avoiding having their bank accounts frozen. They don't impose these requirements just for fun.
