Thought I would ask here before opening a support ticket in case someone has experienced what we are seeing. Basicly, some of our cms administrators (not authors) are having issues with the EPiServer internal search. It returns results for some users but not others. If a user who is having the issue logs in as another user on the same machine/browser/etc. then they are able to get results. This leads me to believe it's a permissions issue but after looking around for awhile I can't find a place where those permissions could be set.
I would start with doing a reindex. http://<yoursite>/EPiServer/CMS/Admin/IndexContent.aspx if you haven't already tried it.
I might remember wrong, but i think episerver do index access rights as well. So that you do not end up with a search result showing documents you should not be able to read.. If i am totally wrong I sugest a reindex as Per mentioned. :)
Are the users having the same access rights?