This sucks, but in the four years we have spend talking abotu it, no one found a way out that will not break a few million existing wiki pages.
The simple (albeit ugly) solution would to add a parser version field to the revision table, drag the old parser along as 'legacy', make the new parser the default (and only) option for all new edits, and spit out a warning when you are editing a legacy revision for the first time. The warning you be made dependent on the cases that break with the new parser. Cases that break could be detected by comparing tidied HTML output from both parser versions.
Nah, well, now slam me for not reading through four years of discussions and finding out why my proposal is dumb ;-)