Yes, one Attack of Opportunity can potentially prevent another, or make it pointless.
Although Attacks of Opportunity, Immediate Actions and Readied Actions interrupt the flow of combat, they still occur in time order.
There are no rules specifically for order when a creature provokes an attack of opportunity from more than one opponent. However, it's reasonable to assume initiative rules apply:
If two or more combatants have the same initiative check result, the combatants who are tied act in order of total initiative modifier (highest first). If there is still a tie, the tied characters should roll again to determine which one of them goes before the other.
Once that's been established, have the creatures act in initiative order. If the first to act kills the enemy, then the second character no longer has an opportunity, at least not against a live opponent. There's nothing preventing him from taking his attack of opportunity, but it may be futile.
Is their AOO for the round used up now?
Not unless the second creature attacks. The second actor doesn't attempt to attack and then get interrupted. The circumstances change before the attack.
In the case of the immediate action, the rules state:
Much like a swift action, an immediate action consumes a very small amount of time, but represents a larger expenditure of effort and energy than a free action. However, unlike a swift action, an immediate action can be performed at any time — even if it's not your turn. Casting feather fall is an immediate action, since the spell can be cast at any time.
So, once again, if the order of Attacks of Opportunity is determined and the first attacker misses, triggering the cleric's immediate action, then the second creature no longer has an opportunity as the cleric is "away".
And also, once again, the second actor doesn't attempt to attack and then get interrupted. The circumstances change before the attack, so the AoO is not used.
