We have the same issue with one of our clients.
The indexing gets to about 95% on the problem users and shows this error, over and over:
Error during indexing, invalidating index: System.ArgumentException: Illegal characters in path.
I don't see where the path is invalid, as the email itself works through the web interface.
Other users on the domain also work for searching. It is just 2 out of the multiple users that cannot.