Hi Leon
Ive not actually animated hair as such but Ive had that problem when setting up hair using mayas built in tutorials.
I think its to do with how the paint FX hair is applied to the folicle curves as when its animated in the viewport the folicles do collied with the head but the actual paint hair goes through the head.
I think theres a setting that "sticks" the paint hair to the curves more that might help you out, but I found you need more folicles to get a nice covering of hair.
I generally make the hair from a nurbs cap so to speak, that I then make curves form that are then the folicles, so for an animation (ive not tried it, but it might work) I would be tempted to try to make the cap a softbody and make that collied with the head as this would then control the curves and then the folicles (as the history is on) and then see if that would work.
"No pressure, no diamonds" Thomas Carlyle