“What I’ve come up with (deep breath — be gentle) is that the store works out which components will need to be updated.”

That’s not bad. It actually sounds like an ideal job for mobx. Using an observer library to rerender minimally sized DOM fragments makes DOM diffing largely redundant. VanillaJS + mobx + a shim to diff collections would probably be great.