are directory updates taking along time?? you may have a message that is causing the bottleneck.
create a mail profile to access the content of the directory mailbox
1)ensure raw properties are enabled.
2)under server, highlight directory services and select raw properties
3)go down to OBJ_DIST-NAME and highlight and copy the contents of the edit name box.
4)open up outlook and create a new profile, and paste in obj-dist-name into the mailbox name.
5)you will need to log in as an administrator.
you will now be able to check the directory and make necessary deletions to stuck messages.
hope this helps