About at the same time Google Japan added
5 new features [webmasterworld.com] (dictionary, company info, stock info, train info & parcel delivery info) it also seemed to have changed from Shift-JIS to Unicode as the default encoding. What I understand from
this page [forest.impress.co.jp] is that until April 22 a query sent with a hexedecimal encoded kanji/kana character in the URL was decoded by Google as Shift-JIS string, while it is now by default interpreted as being UTF-8 (Unicode). Adding '&ie=Shift_JIS' (input encoding is 'Shift-JIS') to the URL still works OK.