@Andres, Arunas: As I mentioned above, there are a number of store-related issues which will cause the "recovery partially succeeded" error, and the only way to really resolve the problem is through a support call. If you want to track down the root cause, you should open a case with Microsoft Support who will help you configure tracing and analyze the results.
@Der Eisenmann, Andrei G: Thanks for the feedback. :)
@MikeBaker: Thanks for the comments. You're absolutely right: a lot of customers use mail-enabled public folders as a workflow or feedback mechanism. As a matter of fact, I "cut my teeth" at a company in Denmark who have the world's largest public folder environment and are known within Microsoft for using PFs as just this type of workflow mechanism. But let's be clear: the recovery mechanism I outlined in the blog is for those cases when you can't recover via Outlook or ExFolders. This procedure is for situations when you have no choice but to recover from backup (which usually means you're in dire straits) and need to do so accurately and effectively.
So on to the technical details ... If you clone a mail-enabled folder, the alias will most likely have a number appended to the alias, so mailfolder would become mailfolder1, and its email address would likewise change from mailfolder@tailspintoys.com to mailfolder1@tailspintoys.com. This occurs because Exchange won't allow you to create two objects with the same alias, and the email address is built on the alias itself. End users never see the alias, just the folder name, so this doesn't impact them directly. [It's this same alias shift that would lead to the problem with distribution group membership.] You could probably run a script looking for numerical values at the end of the email address (presumably using a regex), enumerate those objects, and then perform a name change operation against them. I know this is less than optimal behavior, but again, you should only perform this sequence if all else fails. It's not the preferred option (which would be a quick and clean undelete with Outlook or ExFolders), so may entail a little cleanup afterwards.