I will try and find chkds, but it will take some time, I think.
--turn up Diagnostic Logging on Directory Replication, you may be able to locate what are the corrupted objects in the App Log, then delete/recreate them. You will find certain events that will tell you exactly what the corrupted/orphaned objects are, i.e., mailbox, custom recipient, distribution list, etc.
--if the Site has remained stable, you haven't add/deleted 100s of mailboxes, you can restore an older Directory on the suspect server. If the one you rebuilt is 1 week old, restore a 2 week old Directory. You will not have any mailboxes that were created between that time. Don't mess with the Store, just the Dir. You can restore 3 month old Dir, 6 month, 2 yr old Dir, it doesn't matter, it will talk to the other 5.5 box in the Site and become updated (Update Now), however whatever specific mailboxes that were created AFTER backup date of Dir, will not be there.
--you could even save Priv and Pub.edb from Bad server, then delete it from Site, then reinstall it, selecting to JOIN existing 5.5 Org and Site, the drop in production Priv and Pub, then do DS/IS Consistency Adjuster in Exch Admin, to populate blank Dir w/ mailboxes in Priv.edb.
There are other options as well. If you're pressed for time, go to Microsoft's News Groups and post for Chkds, I'm sure one the MVPs or someone can find it for you.