To be honest, I did not have much more problems with the average flying head compared to the average bird-headed guard. In both fights, I often take damage, but deal more than I take. Timing is usually enough… The only really hard ones (that deal 3-4 points of damage in a single bite) are those that guard the life-extending potions in the second and third ruins levels, but they are optional.
I have never known any version of PoP1 or PoP2 to be speed-sensitive, but to be sure I played it as extensively as I could today through DOSBox as well as on my K6-II “real hardware” system, and found no differences.
However, I have a possible explanation – have you by chance been playing the “initial release”? This is the one where cheats are activated using “prince makinit” and if you press Alt+V it just says “Prince of Persia 2” without a version number?
If so, then this might be the problem – I’ve played this version a bit today, and found that I am much more likely to miss running jumps in this one compared to the newer “1.0”/”1.1″, and also the goblin heads may have been out-of-alignment more frequently (although I’m not 100% sure on that one).
So it looks like they really did fix some subtle bugs (in addition to the obvious ones) in the final releases.