Hey, I have a user with a 8703e. He has about 700 contacts. When he goes into his contacts and enters a letter, it isn't filtering properly. Sometimes it says no addresses, and sometimes it pulls out 2 or 3 when there are more that should be in there.
possibly corrupt address book database? possibly user error...(they always lie!)
try deleting the Desktop[SYNC] service book from the BB, use DTM backup/restore advanced to delete the address book database, and then repush service books from the BES.
This, ofcourse assumes there's a BES in the picture, and that all the addresses are in the user's mailbox