I am only able to search by first name and last name. These are not always incorporated within the actual usernames. I have contractors where the username is related to the contracting company - acme1.contractor, acme2.contractor, acme3.contractor etc. This helps with data protection because we don't want names of individuals burnt into data tables by edit tracking.
There are no returns when I search by "companyname". This makes it difficult when add a new user associated with a particular company because I need to know the numbers included in the username that have already been used. The work around at the moment is to use Admin Tools for ArcGIS by Geojobe. Using categories helps but only if they are applied consistently.