A Public Address book would be more reliable. Can you create one on the Public Folders and allow only your boss & qualified personnel access to it?
There is only one issue with this solution. That is this is happening for all contacts, sent item, inbox items and any other serachable item within the particular mailbox. So any further input would be greatly appreciated as this is really starting ro annoy me.