Display Names 'disappear'

I have some users who are having some Outlook 2003 display name problem. It
is only happening to external STMP addresses.

They can see the names on incoming emails, can see the names when they hit
reply, but when they send the message the display names of all the SMTP
addresses not in the GAL or their PAB are blank.

If you double click on where the names are you can see their address but the
display name shows up as just as a quote (") smybol.

The messages are going through. We are using Outlook 2003/sp1 with Exchange
5.5/sp4

Thanks,
Jimmy Quan