I have never played Brawl myself, but from the vids I've seen, it seems very well possible that the computer AIs DO learn to some extent. I'm a programmer myself, and I would like to bring in some opinions.
First, the argument that AI inputs are not recorded in replays... I'm not sure. But the file size is *not* a good indicator for that. Actually, even without using any compression, recording another player's input takes up a few kB extra at most, which is nothing compared to today's harddrive sizes.
I think some people tried replays where the gameplay is changed (no tripping or whatever) from the original recorded game. I think this is a more reliable test. If all the inputs were recorded, that would mean a desync of all players would occur at some point. The players would start doing random stuff. If no input was stored, the human players would desync and the computer players would not.
However, this test still doesn't bring 100% certainty. Imagine this: Every character has 64 slots to store "learned sequences". This data contains when to apply the sequence, when not to apply it, the actual sequence, etc. Now, the replay could actually contain this information, couldn't it? When the replay file is loaded, the computer loads these behaviours. This means that no matter what stuff your *current* character has learnt, it will be overwritten by the replay so that no desync will occur. Over all, we can say that there are many ways to overcome the problem of the computer AI always having to do the exact same things in a given replay.
About the actual "learning" process. It is true that the computer players will not reach our level just from watching us play. Computers are perfect at reflexes, efficienty and precision, but they SUCK at dynamically handling a new situation and at creatively reacting to it. Also, the computer fails to understand what exact purpose a sequence has. Still, it is rather simple to make an AI that will record your best and most used sequences and that tries to use these. But, because it is uncreative in applying them, it is not able to reach our level of play.