The DS/IS Consistency Adjuster is normally used after restoring either the Directory Store or the Information Store. It is very important that you understand what the Consistency Adjuster does, and how it can affect Exchange, before using it - especially if you have more than one server in your site or have a site connector configured with public folder replication.
The consistency adjuster will:
Create directory entries for mailboxes that don't have them
Delete directory entries of public folders that don't exist in the IS
Remove from the IS permissions of users that are no longer valid
If what you want to accomplish is not listed here, don't run it.
You do not need to stop any services to run the Consistency Adjuster.