We had an issue recently when we migrated some exchange 2003 mailboxes onto an Exchange 2010 (Please note Exchange 2010 was SP1) Environment.
Basically after the migration all migrated users using Outlook in online mode could only see a blank Global Address List.
After looking into the issue we found that the resolution was to clear the value from the following attribute “msExchQueryBaseDN” via ADSIEDIT for the effected user.
After clearing the value the GAL suddenly appeared correctly
I believe Microsoft are looking into sorting this issue in Exchange 2010 SP2.