No. I wrote up a pretty decent argument for why they don't:
http://allisbrawl.com/forum/topic.aspx?pid=569180#p569180
Yeah, its a pretty good argument, but the issue is that I'm not sure if you can pull "Absolutely no CPU data is recorded" from "replay size is fairly small" and "CPUs have been observed to use AI in real-time". See, just because CPUs use AI in the times where we recorded it doesn't mean they CAN'T pull actions from other sources, and "fairly small" is relative.
Many of these reported "learned" chains are quite short, such as "jump, Reverse Falcon Punch" and "dusk, stand, duck, stand, duck, stand". What if the replay data stores information like "at 1:23, stop CPU AI, input duck, stand, duck, stand, duck, stand, resume CPU AI"? Such info could easily be inserted while keeping the data size "fairly small". I don't believe any of those "trip" videos have any actions that resemble "learned" actions so we don't know what happens then (as of now).
From the points you have presented as of now, I don't think there's any that shows the above is impossible.