It was not an old wives tail. I worked in wireless retail 23 years ago and saw these problems first hand. NiMH phone batteries from that era would scarcely last two years. Of course, it mattered less then because the tech was improving so rapidly that most people wanted a new phone every 2 years anyways. NiMH was an improvement over NiCd, but it still had memory problems nonetheless in its first few generations (modern NiMH batteries are better at this).

It could be mitigated by fully discharging a battery before recharging, and I'm certain that in applications such as satellites , they engineered the charging cycles to mitigate this. However, consumers powering phones and laptops can't be expected to maintain such discipline. Certainly people driving cars over variable distances can't be expected to uphold such requirements either, out of absolute necessity to travel a fixed distance between charges.

Lithium ion ultimately won because it solved these problems altogether. Modern NiMH has caught up a little bit, but Lithium has meanwhile improved as well.