AI OnAI Off
What is your database collation? Maybe that could cause the problem. What I would most probably do is to enable EPiServer logging (usually episerverlog.config file), then run Sql Trace to see what EPiServer is executing against database and see what is the result coming back. Then there should be more light on issue you described.
If you search against a AD Provider that will explain it.
Episerver adds % before and after the name mcheck this post
http://world.episerver.com/Modules/Forum/Pages/thread.aspx?id=26441
When I go to CMS > Admin Mode > "Search users" and search for a name or email address, 95% of the time I won't get any result even though my search criteria is correct. Even a search for just the letter j won't get ALL users with the letter a. However, pressing search with the name and email address blank will display all the 150+ users we have.
Is this an EPiServer bug? or just a configuration issue? I'm using the latest CMS6 and relate.