The final version of execution replay that I did was for Xen, which had the asynchronous device drivers. In that case, the goal of the drivers was to have the device do DMA directly into the guest's memory space, and thus had to be modeled as an external processor. If you were content to modify your virtual devices to always doing copying, it would be significantly easier.
But yeah, in both cases you just have so much that the thing underneath might be doing, it's hard to tell which is going to be more fragile. :-)
The final version also did multi-processor VMs, using the paging hardware to track sharing across virtual cpus [1]. The key take-away from that was, "It's slow, but often not as slow as you might think."
[1] https://www.semanticscholar.org/paper/Execution-replay-of-mu...
It probably is easier to debug rr replay bugs than VM-level replay bugs, partly because rr is lighter-weight. rr replay bugs are still insane, but it's all relative :-).