I had a similar problem (1,300+ authors and growing) but my solution takes a slightly different approach.
For the front-end, I made an A-Z “list authors” page (https://writing.navyhistory.org.au/list-authors/)-IMHO, this is much better than a search; it’s driven by a simple no-frills plug-in based on code for wp_list_authors.
For the back-end, I use Manage-Me (a plug-in by stilglog that’s not published anymore). I made a small amendment so that when you look up the user name, you also see the user ID.
BTW, works on 2.1.3 and 2.2.1
I’m no expert, but happy to make some/all available. Send an email from website and ask for it to be forwarded to Ted.
Ted