I believe the MSN data goes back to 1994 or so. It's HLCV (no open), and I believe that the very earliest MSN data is close only, no volume or high/low.
There also aren't any delisted stocks, so if you build up a historical database from that data with an eye to backtest some trading strategies, be aware that survivor bias will be a major problem if you go back more than a few years.
You can compile a list of current Tokyo issues from the TSE website; you can also keep track of new listings on their site:
Reuters Datalink for daily and Quotecenter for some historial intraday http://www.equis.com/products/data/ adaptor for TS 2K available form itservice.net