Great idea but did not work. Here is what I discovered, hopefully this will be enough of a clue to fix. I added a new contact and that contact and that contact ONLY can be found via a search. So it would appear that my BB is not seeing anything that already exists, only new contacts. I am using hosted BES. The other day my provider had me delete and then undelete my desktop CMIME service book in case that is what could have caused this.
Any further suggestions? It seems like I just need to "reconcile now" or something like that, but I cannot find any such command.