My intuition suggests that all of these documents being on lined paper would make the problem quite a bit easier, by providing clear features that have to line up between fragments.

At any rate, it makes you wonder if most documents are on lined paper, or if it's more common to see things on, for example, white printer paper.