Wait, what countries don't use these? At least in Canada every restaurant that isn't fast-food is going to give you the receipt and change on a tray or in a leather booklet.
Funnily enough I was just at a 7-11 in Tokyo about 30 minutes ago, just as you were writing this comment, and before I had read this thread. I happened to notice that such a tray was not in use there, which felt more efficient. Of course 7-11 is mostly a franchise business, so it may the store owner's decision.
Which one? I think it is more likely you just missed it. I've never noticed a convenience store without one, though now I guess I will be looking out for it.
Just north from Suidobashi station, Mita line, North exit.
The till nearest the door. It was a male Japanese cashier (unusual at that store) who seemed particularly dynamic. Possibly a management trainee.
But at least in my experience they are not very common for giving change in shops.