PIN lookup is only available within a BlackBerry Domain (also referred to as the configuration database). In your configuration, you have a shared Active Directory domain, a shared Exchange organization, and shared BES service account (I'm assuming), but separate configuration databases. The way to get this working is to use the same backend database. For remote sites over a WAN, this may not be the best solution.
For example, our Atlanta users are able to do PIN lookups with other Atlanta users, but they are not able to look up PIN numbers for users at our New York or DC or International bureaus, and vice versa.
I'm sure this will change in the future, out of the box, most likely through a replicated attribute from the SQL DB to AD. To be honest, there may be a way of doing it now, although it'd take a little leg work. You could do an export from the SQL database(s), use LDIFDE or some other tool to merge the PIN information to an AD attribute in a batch job, then do PIM mapping to map whatever the attribute is in AD to the device contacts PIN - although its the lookup part that may or may not work, as that may very well be built in to the Lookup function. Anyhow, just thinking out loud