I am using an OnDemand instance.
There are 3 users who cannot be searched in Confluence in autocomplete mode. But they show up when searched using the people directory.
The other interesting observation is that only these same 3 users show up more than once in Confluence People directory. So, I feel its related to them not getting popped up in autocomplete search while assigning them to pages/messages.
They popup in Jira in autocomplete search.