Check out this article from RIM: BlackBerry Search Results
You have the dreaded Send As issue, either this user didn't inherit the permission or they are in a group like domain admins that lose this right due to their group membership.
Read thid article and double check the permission in AD and group membership.
Wireless sync uses different permissions then email, email is accessed using the Send As permission on each user object. So, some can have and others will not. Usually the user has inheritance disabled for some reason or they are in a group that loses this right.