I don't think the problem is AI.
Think about the games we're mentioning with co-op. Each level was simply a map. When that started changing co-op started disappearing. Putting co-op in a Build engine game was simply creating another spawn point. The levels functioned identically to DM levels.
Think about HL. The levels are tiny with no real beginning or end. If player A walks into a new level, what happens to players B and C? Can they still see him? Do they get taken to that level as well?
Obviously not all games have this, especially with levels getting bigger, but I imagine they have their own issues.
Did anyone ever try one of those Far Cry co-op mods? Now that sounds like fun.