The interface between userspace processes and the kernel and CPU is pretty complicated. It's hard for me to tell whether it's more or less complicated than the interface between guests and the hypervisor (given most record and replay scenarios don't require virtualizing exotic hardware).
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 :-).
My first prototype of execution replay I implemented was for Linux processes (in like, 2000 or something), which I did by modifying Linux. The primary thing I did there was to instrument copy_to_user().
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."
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 :-).