Super simplification of the whole concept: You can do AI on asynch, it just can't be as complex or numerous as lockstep. Which is the pitfall.
On asynch, each AI takes up the bandwidth of a normal player. So 4 people playing against 12 AI would be like playing a BTB match (roughly). MS also has bandwidth limits, so you couldn't add much AI.
On lockstep, all you're networking is button presses. So it doesn't matter if you have 4 AI or 30 AI, your bandwidth cost is the same.
Good summary. However, even there are definitely ways to do asynchronous with AI that doesn't mean that the AI uses the same bandwidth as a player.
The reason why the campaign and co-op multiplayer uses synchronous lockstep networking is because it is the easiest way to synchronize code that was original written to be run on only one machine (A.I., physics, etc). Each player's console is essentially running a copy of the campaign / firefight as if it were running locally on their machine, with 4 players playing locally and some synchronization code to keep the controller inputs the same (over simplification of course). The game was written to be completely predictive - that is if you press a button on your controller when the state of the game is X the game will always do Y.
Now, I'm not saying it's easy, but the game could be rewritten such that asynchronous could be done without each AI taking up the bandwidth of a player. Instead the host would synchronize AI state (I'm moving to this position, I'm firing at this player, etc.) when the state changes rather than constantly sending a flood of millisecond updates about position, orientation, etc for each AI. Then of course the client consoles would have to run client side simulations based on the last known state, and correct the simulation as new updates arrive from the host.
It gets even more interesting if the "ownership" of the AI is based on which player is closest to the AI, who the AI is focusing its attention or, etc. allowing the peers to actually choose which console is controlling the AI to give even better response times for the player who needs them most.
Anyhow... yeah. Perhaps we'll see it someday in Halo. Or not.