Hi there - we have 4500 employees in the primary GW address book, so when we set up the synch on the BES we select the user's Frequent Contacts book (hint: make sure the setting to allow duplicate names under options in the address book on handheld is set to NO). Lookup feature is then available for the rest of the address book.
You need to stress to users that the BB does not provide full GW functionality - existing groups or orgs in the address book will not be available in the personal address book or in lookup. The groups option on the BB lets users set up groups to use from the BB to replace the ones they have on their desktop
Bluetooth headset - we have been using the Motorola HS850, seems OK though the device is dropped occasionally.