[snip]
Thanks for the explanation! I think I understand it better now. It's basically because Mt. Gox stores its user's USD, EUR etc. and needs to transfer these funds to Mt. Gox in Japan that it needs this license.
So wouldn't the solution to this be to not transfer the money between countries? Ie. have a different exchange in each country and then an exchange would only need to store (and not transfer) the users' funds.
A group of people in my country of residence (Denmark) is trying to set up an local exchange (Copenhagen Bitcoin Exchange (CopBE)) which would (unless they charge fees for deposits) be free for me to deposit money to (since my bank takes no fees for domestic bank transfers). They've written that they have applied for a permit that gives them "limited permission to store electronic currency". So it seems they don't have to become registered as a bank because they're only storing currency, and not transferring it between countries.
As far as I can figure out, an option for Mt. Gox could be that they buy this exchange (CopBE), make it a part of Mt. Gox and then they'd have Denmark covered. Repeat for each country in the world.
I don't think transferring the funds to Japan specifically is the issue. It seems more to be that it receives, holds, and transmits money
belonging to others at all. Many countries require licences if you're doing that even if all of the transactions are purely domestic.
I also think that people are vastly over-estimating the capacity of the exchanges to fight protracted legal battles in foreign countries. Such fights are extremely expensive and all of the exchanges are relatively new. While their turnovers might look big, I suspect that none of them have hundreds of thousands of dollars which they can afford to gamble on court cases they may well lose. For them to continue to exist at all, the exchanges must remain financially viable for their owners.