Yesterday at Moodle HQ we were discussing about this issue. But we didn't agree anything.
Personally I think that the "initials" and "search into everything" old methods were really usable (although not too much accessible). In the other hand, the new filter-based approach is enormously powerful sometimes (when you don't know the name/email, or want to make some special searches).
So, the key here is if we all want the both systems to exist and how we make them to co-exist? Assuming all we want both systems available... what would be the better way to do so:
1) Simple put both together, one above the other, unrelated?
2) Make the old approach the default one, while putting the new one under the "advanced" switch?
3) Add the old one (initials) under the advanced settings (note it's really supported now "name begins with...) with the old interface? And make the "simple" search to search both under complete name and email?
4) Add some setting to decide what system to use, making them exclusive?
I really think that's the key. Both methods have fans. Feel free to comment how to integrate both. Also, some accessibility solutions for the initials should arrive, but that isn't the objective of this bug.