Given this thread was about Kyoto and went to Tokyo quickly:
Osaka Shinsaibashi was 8k and now 12k, very centrally located.
Tokyo still has some at 8k.

I think Choice Privileges is the best deal for hotels in Japan, given how high their rates are now. 8k with points at 0.6 cents each (with one of their frequent sales, the better sale would be 0.5 cents apiece) is $50 US.

I would say you can also look for deals by trying to get bigger than base rooms. For example Comfort Inn Kyoto Horikawagojo has a 3 bed room for 16k, which is more but was very spacious and very comfortable (and also had a view of Kyoto tower), though a bit more than a base room in cash was the same in points.