"I've never seen a rental that's not a ripoff. Sims can be bought on every street in Japan from what I recall, but I didn't shop. I think you'll do fine. See the algorithms above for finding companies if you want to pre-check on the web."
In Japan maybe, but in Europe things are moving...
Check this for Germany:
www.rentmyphone.com