Microsoft's TTD (a user-level tech) does allow genuine parallelism, I believe. But my understanding is that it has slower (though still very impressive) single-threaded performance as a result, so there's a tradeoff. But perhaps you could do something more like that.
We believe it's possible to handle parallelism in record/replay tech while still having good single-threaded performance - but it implies a much more complex implementation to do so safely.
[1] https://msrc.microsoft.com/blog/2019/05/time-travel-debuggin...
[2] https://www.usenix.org/legacy/events/vee06/full_papers/p154-...
And we don't handle unrestricted multithreading in rr. If we wanted to it would complicate things a lot and I don't know if existing kernel APIs would be adequate. We're skating along the edge of feasibility as it is.
Once you are in modification land it really depends on the kind of hypervisor and its implementation. Like doing it for a OS, a well-designed, consistent, and tight interface makes it pretty easy. But, the unconstrained multithreading for multicore VMs makes it problematic for record-replay solutions if you do not want to serialize.