I don't think I've ever seen a Travelex booth in Japan. Those are the guys to go to if you want to pay the MOST for foreign exchange. The Travelex booths I've seen in both the US and UK, whether at airports or in shopping malls, all seem to charge about the same: you lose about 14% of the value using their "no commission" exchange rate.

All of the airport forex booths I've seen in Japan charge about the same: converting from USD to yen, it's 0.5% for travelers cheques, or 2.5% for cash. From Yen into USD, 2.5% is charged. I've never seen it vary much from booth to booth, or over time. Put another way, Japan is the only place I've been where you can just exchange currency at the airport in either direction, and not have to be on guard for a ripoff.