I tracked a sample movie clip and put a cube in the center. It animated quite well, and I was even able to see the video by playing (Render > Play) a set of PNG files.
I then changed options to export to H.264 and the result was quite bad - it looks like I somehow created a lag between the camera tracking and the video. It seems object on frame X is shown as if the camera is on frame X + 1, so the object moves just slightly ahead of the video.
What did I break?