Or in the less-than-worst case you could cache the created full frame if no native full frame is encountered for X seconds and then in the worst case you don't

Or in the less-than-worst case you could cache the created full frame if no native full frame is encountered for X seconds and then in the worst case you don't have to go to the beginning of the video, but to that cached intermediate full frame?