Hi,
We have more than 10.000 users. So, the ability to search an user by full name or login or any other attribute related to the user is a major issue for us. Considering that this issue is more than 4-years old and that there is no solution neither a comment from Atlassian so far, we have decided to investigate the source code to check how complex it would be to implement this "minor" feature.
Believe me! We, that are not JIRA developers, have taken less than 2 hours to understand the logic, modify the source code and put it in production! Of course we don't know if it is OK from Atlassian stand point, but it is working for us! 
We would appreciate a comment from Atlassian saying if the patch can be used for other users and if they plan to include this patch in future releases.
So ... here is the patch for the JIRA 3.13.2 Enterprise version. It may work with other versions too, but you must test before putting in production mainly if you are using a different version.
- First, backup your files!
- Replace the userbrowser.jsp located at <JIRA_HOME>/atlassian-jira/WEB-INF/classes/secure/admin/user/views/ by the attached file.
- Replace the UserBrowser.class located at <JIRA_HOME>/atlassian-jira/WEB-INF/classes/com/atlassian/jira/web/action/admin/user/ by the attached file.
- Restart your JIRA instance.
- If it won't work, restore the files.
- Have fun!

Hi to all,
JIRA has had this ability for a few releases, from at least 4.1.
Sorry that we did not resolve this issue earlier.
Cheers,
Roy