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.