This is something I began to notice a few days after I got my copy of Brawl.
As a CompSci major having already taken and passed an AI class, I have to say that it's not impossible to have CPUs "learn" in this case.
If there were an infinite number of individual moves that a character could use, then it would be impossible. If there where a very large number of moves that a character could use, then it would be difficult, hence the difficulty in having complicated robots in this day and age.
But each individual character has less than 50 moves to learn from. It is not that hard to notice that some attacks are much more useful than others and then start using those attacks more often.
And quite frankly, I did notice that the Lvl 9 CPU Zelda on my game was seriously starting to catch up with me. I had a trick that I liked to use where I would make Din's Fire explode behind an opponent, causing them to fly towards me while spiraling so that I could have a follow up hit. This could be Zelda's bair or maybe a charged smash but.. w/e. After I used it for a while successfully, I began to notice that Zelda uses Din's Fire a lot more often. In fact it really messes with my camping game when it does this.
But CPU Zelda doesn't use it in the exact same way that I would. CPU Zelda uses it so that Din's Fire explodes in front of me, sending me away. But this shortcoming isn't too surprising. Technically it's still an off-center Din's Fire hit. Most likely, the CPU has some subroutine that says something like...
if(dinsFire.successRate() > SOMEPERCENT)
{
dinsFire.use();
}
Where use is yet another subroutine that has a very specific pre-defined way for using Din's Fire. So it might not really notice the finesse with which you actually use the move. It might just notice that that move tends to connect so that move = win. It's actually a fairly simple addition compared to all of the other AI work you'd already have to do. In fact it makes certain parts of the development easier instead of harder, as you don't have to make some arbitrary guess as to what common tactics are going to be.
Now, saying that it's POSSIBLE and saying that it's TRUE are two seperate things. I don't think we can tell with absolute 100% certainty that it's true or not without doing one of two things:
1) Reverse-engineering the compiled code for Brawl and trying to figure out if this code even exists. This is very difficult because it's like finding a needle in a haystack. Except it's harder because the needle is light brown and flimsy just like every other piece of hay in the haystack. Not really a good method. It could literally take years and I'm not kidding.
2) Keep an eye on the Brawl save file on the Wii to see what data is uploaded and where. This is much easier to do if you can get a program to do it for you. You will likely have to code this yourself. Chances are if there's any way for the CPU to keep track of this, it's in the save file. Also, it's very likely that the amount of data that changes between matches is pretty small. There will be some Time Played data changed, some KO count data changed, among other things. If any of the save data changes, some of it WILL be the success rate of each move, assuming that the code really works this way. It won't be impossible to track it down after this, but all of this work is going to still be pretty hard.
A third technique you could use would be to...
a) Copy your Brawl data onto an SD card
b) Remove said SD card
c) Delete all Brawl data from your Wii
d) Make a new Brawl file
e) Play against your mains, if they're a part of the starting line up.
But this is less likely to provide emperical and undeniable results, but if your main rocks on your real Brawl file and fails hard on the new Brawl file... you'll know.
And I could say more but it's already tl;dr
tl;dr version is...
It's not impossible for the AI to adjust to the player's tactics, and here's a way of possibly finding out whether or not this is true.
EDIT: Well the replay thing WOULD disprove this, so nevermind.