I answered "No, but I do allow Cleave on AoOs."
My reasoning has been explained elsewhere, but I'll reiterate, lest you think this is a clever chance to point at me and say, "Ooh! Ooh! You're contradicting yourself!"
1. Any time you threaten an enemy, it is assumed that you are engaged in battle with them - you are swinging your weapon at them, punching, kicking, grappling, parrying, etc. This is true for all enemies you threaten.
2. Cleave represents an ability to take advantage of a "finishing strike" - the point in real time when the enemy you are fighting falls unconscious, dies, etc., as a result of your actions. This can be described cinematically in any number of ways; it is not limited to "I swing my sword so hard it cuts through Bob and into Joe." It can be, but it can also be "I stab Bob through the heart with my rapier, and as he falls, I guide him into Joe. This fouls Joe's blade, and I take advantage of the opportunity thus presented."
3. An AoO represents nothing more than an additional opening in combat. There are, generally speaking, numerous such occurrences, happening and closing every round. Your ability to take advantage of them normally is represented by your BAB. However, sometimes someone does something that leaves more openings than normal (provokes an AoO). Your ability to take advantage of such an opening is, still, represented by your BAB. (NOTE: I believe being rendered helpless should provoke AoOs but, RAW, it doesn't.)
4. So, why did I say "No," above? Simple. You cannot take advantage of an opening that isn't really there. Therefore, you cannot make an AoO on someone who has not provoked one.
5. But wait, I allow Cleave on an AoO. Isn't this feat the same thing, so aren't I contradicting myself? Not at all. Cleave is the ability to create an opening where there wasn't one - by hacking through Bob and into Joe, by tossing Bob into Joe, by spraying Joe with Bob's blood, by attacking from an unexpected direction (his blade should have been over there), etc. So, someone with Cleave can create that opening, even if the "kill" happens outside of his or her turn (which is a metagame concept, anyway - that character is constantly attacking and constantly defending, even if we need to segment it out to make the game playable).