Oh I knew they were solvable, the question was more whether I had the time/motivation to implement them (and test them)!
I'm actually surprised the current parsing technique (all on the EDT, multiple parsers will parse sequentially so their run times are stacked) actually scales as well as it does. I'll admit the only times I've tried it with "huge" documents (hundreds of thousands of lines) has been simple test cases with the RSTALanguageSupport Java parser just to get a feel for performance. Things seemed more than fast enough for the common cases, but I know that's highly machine/environment dependent.
In any case, I'll be happy to explore better parsing handling moving forward. Your idea of using hashes to determine out-of-date content is a good one. I also like the idea of being able to toggle the current, synchronous method and the asynchronous one, but that would also mean maintaining two different implementations.