The ABSOLUTE BEST Japanese IME for mobile devices is a little known program called Decuma Japanese. With Decuma, you just copy down what you see (correct stroke order helps but isn't required) and it turns it into Japanese for you. It is very fast, very accurate, and you can use it on non-Japanese PPCs (Palm version also available).
It is much better than the built-in IMEs, even better than that of a native Japanese PPC, IMHO. The one problem is that getting the Japanese version is a little difficult - I had to have the help of a Japanese friend to purchase it since its only through an all Japanese site - and navigating the order system was impossible for me. But here are the links:
general info:
http://www.zicorp.com/DecumaJapanese.htmtrial version/ordering:
http://www.zicorp.com/eProducts/Decuma/?page=decumaJapaneseA program that I've had god luck with as a dictionary on the PPC is by Ectaco. It isn't too big and it runs pretty quick. It does not have all the words that Jim Breem's dictionary and others, but it has most everything I look up. It comes with an IME so that you can use Japanese input (multiple input options, like kana or romaji conversion). This is the IME that I use when I want a keyboard for input rather than Decuma's handwriting recognition.