I've noticed the same thing as well. The post battle screen after exiting also tells that "Battle link not found." and the replay can't be found even by browsing through the collected replays. It seems if there is a team consisting entirely of AI, a replay is somehow not saved. It doesn't seem to depend on the type of AI either as matchmaking still uses CAI while most custom battles already use Circuit.
Also, these battles give no XP for the players either. I'm still experimenting to determine accurately in which cases no XP is rewarded but at least when no replay is formed no XP is given either. So far evidence suggests that this concerns most Co-op games even when starting via Chobby matchmaking.
This is a shame especially for beginning players as Co-op is a more rewarding training platform (as you usually don't get commsniped or focused down as easily as might happen in team battles or FFAs).