Well, should AoOs, by default cause the provoking action to fail? Do not pass go, do not collect $200, do not pay the feat tax, do not give foes a reflex save to negate.
Someone moves out of one of your threatened squares? AoO, and if you hit, then they don't move.
Someone tries to chug in potion in your face? AoO, and if you hit, the potion is wasted.
Someone tries to cast a spell in your face? AoO, and if you hit, the spell fails.
With this ruling, I would say that Bull Rush, Disarm, Grapple, and Trip do not provoke attacks of opportunity, nor does making an Unarmed Strike against an armed opponent. I think it might also be prudent to do away with Combat Reflexes, saying that all characters get 1 attack of opportunity per round + 1 per point of his/her Dex modifier. Finally, it would probably also be a good idea to use 4e's concept of Threatening Reach and make that a feat, so that creatures with reach don't threaten beyond adjacent squares unless they take a feat to do that.
All of the above makes AoOs more useful and also makes reach weapons slightly less useful, seems like a good compromise. However, none of the above necessarily makes AoOs more deadly. Should deadly AoOs be the purview of the Fighter class? Or should deadly AoOs be something that must be granted via feat specialization (which could still make the Fighter quite good at getting there)?