Algorithm for recovering paired lists when elements are broken
Look at the literature on algorithms for the shotgun sequencing and shortest common supersequence problems.  It appears that your problem might not be exactly identical to them, but researchers have developed sophisticated algorithmic techniques for handling this kind of problem.  Therefore, I suspect you might be able to use the same techniques for your problem, or adapt them to work well for your situation.