@Karsten: It may be possible for third-party tools to increment the change numbers on individual folders to ensure that they're not re-deleted after hierarchy replication. It's more likely that the tool simply copied the folders (creating new ones with identical names) into the database rather than actually restoring them. Part 2 of this blog (which should be out soon) will go into the mechanisms of replication - hierarchy, content, change numbers, change number sets, replication, and backfill.
@Exfolders: From reviewing the thread it looks like there are multiple issues being discussed. There was a MAPI recovery error, which was resolved in SP2, but there's also a large number of store issues (which often prompt "Recovery partially succeeded" and can't be resolved without tracing and thus a support call).
@Robert: You should be able to find pukka shells in the swap meet across from Aloha Stadium on Wednesdays and weekends. :)