It never even occurred to me to question this rule. We have always played cleaves (and great cleaves) off of AoOs. There's a phrase relating to Warhammer 40k, 'fluff ain't rules'. If you think too hard about it, about what an AoO is or cleave, and are a slave to the tiltes of the rules, they often dont make much sense. It's just a name for a rule. Like not all assassins have to be 'assassins', not everyone who fights is a 'fighter'.
Take cleave, for example. To really go by the name of the feat you should have to use the attack on an adjacent foe to the one that was slain. But you don't. You can happily bounce all around you're threatened zone, 'cleave' right past people into people you want to hit. And who cares? It works. Combat is still pretty abstract. The rules are the rules, the description of how it happens in the game isn't always exactly what the rule name says. Don't let that limit how you interpret events. Just roll with it, mang.