It seems like there should be at least some manual override (assuming there isn't one already - I didn't check the details much beyond the article provided) to set your 'my DNS is NX-LYING' flag manually. For machines that are permanently emplaced in a broken DNS network, it can just be turned on and left.

Roaming devices might make it a bit more tricky, but some integration with OS connectivity-detection and location-awareness might help there, as well as an improved UI for actually setting it.

A really short-term bandage would be to use some less identifiable DGA, but that opens the possibility of future malware using the Chrome DGA to pretend to be legit.

Is there a technical reason why 'foo.invalid' and 'bar.invalid' (and any of the other restricted dns names) couldn't be used instead?

I suppose that the ISPs could serve those correctly to make the tests pass, but what would they gain from it except even more user irritation?

Anything I'm missing?