Hi Vavs,
One thing I would check to narrow down where the problem is, is whether it shows up in Outlook Web Access.

OWA Address Book is the live Exchange version so if it shows up there, you will know the problem is with the local Outlook copy not updating, otherwise if it still doesnt show there then the problem is with it updating on the server not the Outlook local GAL copy.

I'm no where near an expert but hopefully it will help someone give you an answer.

Paul