Saw a strange GAL problem today with a new SBS 2003 install from a few months ago. We didn't see it at the time but the GAL wasn't updating. The first step was to go to System Manager and rebuild the list the list under the recipients update service. Then restart the MTA stacks.
Since that didn't work we deleted and recreated the Gloabl Address List. Now the server GAL showed the new list properly. Next we went to an Outlook client and went to see if it updated. It didn't so we deleted and re added the offline GAL from the server. We then logged off and back on and it still didn't show up. After waiting some time however, it finally updated itself.