That's a good point. I remember having exactly that problem when writing tests for my toy language's parser. Generating random valid programs was actually tricky for several different reasons. In fact, I ultimately gave up on QuickCheck completely for that project, but mostly out of laziness.
Amusingly, I also wrote some tree diff code in Haskell recently. However, I did it rather poorly so I'm going to have to rewrite it soon (probably some time during winter break). I definitely agree that algorithms like this are particularly well-suited for QuickCheck.
However, in other cases, the usage is less obvious. For instance, suppose that you are writing, say a URL parser. What do you want QuickCheck to generate and check? If you generate too broadly, the invariant check becomes a parser itself, if you generate too specifically you might introduce bias again.