Applying this paradox in reverse (which is paraphrasing the wiki article) - if introducing energy efficiency measures causes energy use to go down then someone needs to ask probing questions about what is going on. Increased efficiency should be linked, all else equal, to increased use of a resource.
It's not hard to find examples where this "rule" doesn't seem to hold. If you give me water heated for free, I may shower twice on some days, but I will not take infinite hot showers. If you gave me shoes that cause less ablation of the pavement I walk on, I wouldn't find other ways to remove the same amount of material, I would simply use up less resources wherever I go, being none the wiser.
First example: if lots of people had that free hot water, there would pretty soon be companies offering them money for the use of it. A bitcoin miner hooked up to a stirling engine under the hot tap, perhaps?
Second example: shoe materials are probably fungible for other petrochemical products. Reduced-wear elastomers might result in fewer pairs of shoes wearing out but higher demand in other markets.