I voted "about once a combat" but that's my best guess as to an average. Certain monsters (mindless ones or stupid ones not used to pack hunting) will not have a good grasp on even elementary tactics; they're more prone to provoke, as are things that don't care if they live or die (e.g. many constructs, undead, demons, etc).
A fight with the mercenaries of the Double Javelins is much less likely to have OAs provoked, and will be heavier on the good tactics and battle savvy. The pcs might fight three battles against them and never see an OA... but again, sometimes it's worth provoking in order to gain an advantage, take a ranged attack or what have you.