After more testing, I have found that this is only an issue when the name in the secondry address book matches with one in the primary address book. In domino this would be termed an ambiguous name and the system would return all names. On the BB, this is not happening.
For example...
In this scenario, both contacts are returned fine...
(a) Joe Bloggs, Our Company
(b) Jessie Bloggs, External Company
But in this scenario, contact b is not found at all...
(a) Joe Bloggs, Our Company
(b) Joe Bloggs, External Company
Thanks
