recordmydesktop v0.3.8.1 (Ubuntu 12.10 package)
When encoding on the fly with audio, every dropped frame causes async. One has to fiddle with the fps and subtract some margin to accommodate inhomogenous load, otherwise there are random audio-video shifts in the output (especially for longer sessions where on the fly encoding is essential). This reduces the quality and convenience for making fullscreen/large videos.
Ideally, recordmydesktop would offer to force-sync audio and video, either by dropping audio frames equivalently to video (thus people realise more quickly that their hardware is not up to par) or by extending holes in the video by holding the last image, aka lagging (I think preferrable, since reduction in fps is the least distracting option for the viewer, compared to audio dropping and shift).