AoO's allow you to act reactively to various circumstances. If you remove the AoO system, you could make Readying more flexible to make up for it.
For example, you could allow Readying for a specific trigger without having to specify the specific action to take. Or you could allow Readying a Full Attack (or Move and Attack), provided the character does nothing before the Ready (kinda like a Delay, but with a trigger so it can interrupt an opponent). Or you could allow a Readied character to take his action even if the trigger hasn't gone off yet (can't interrupt an opponent though).
I think all of those changes could easily compensate for the lack of AoO's. For example, if you combine all the variants above, you could say "I Ready an action for when an opponent leaves an area I threaten". If teh trigger goes off (i.e. when you would normally have gotten an AoO plus in 5' step or move-only cases where you wouldn't have gotten an AoO) you get to make a normal attack (but you don't get an *extra* AoO attack) or any other regular action (run away, cast a spell, whatever). If at any point you decide you no longer want to wait for the trigger, you can act at whatever initiative you want (but can't interrupt), just as if you had Delayed you action.
Gets rid of all the AoO problems, incorporates the existing Delay rules, and I think it would streamline combat and make it much more flexible. True, you need a little more planning because you'll never be able to interrupt an action you haven't Readied for, but I wouldn't be surprised to see some fighters Readying more than 50% of the time (because the only thing they lose by Readying is their initiative order).