I've never had a problem with bump maps, they've always worked exactly as intended for me. I've done a few tests with high poly models and extreme distortions, but haven't been able to reproduce your results. It does make me wonder about the complexity of your model, though, and obviously I can't tell that just from the output video you've linked.
The only time I've encountered seemingly inexplicable frame-to-frame 'skipping' in a render is when I've had two faces in fairly close proximity, even when they're static - is your head a single mesh (and I mean the actual head model, not the hat, goggles or eyes, etc), or are you using several (two or more) copies of the same mesh at slightly different sizes, each with varying textures (perhaps to improve the realism of the model)? If that's in any way the case, there are both several causes and several solutions.