Mat's Memories (Theory)
I believe that the soul is directly linked to a person's memories, that rather than being stored in the mind, they are stored in the soul. Or at least in the philosophical and WoT context. Now when Mat carried with him the dagger from Shadar Logoth, we saw that it corrupted him, warping his personality to the point that he was becoming akin to the suspicion that had destroyed an entire city. He was changing. Now when Mat carried the dagger I think that it was like the Mashadar, in the fact that it was slowly destroying his soul. The dagger was an avatar for a more dilute, but no less potent than the Mashadar's soul destroying effect.
This couples with the fact that when a person removes anything from the city of Shadar Logoth they are unleashing the taint of the Shadar Logoth. If Mat had not been Healed the dagger would have destroyed his soul and even while it was being destroyed, the dagger was replacing Mat's lack of soul with something else: the evil of Aridhol to sustain him. Then when he was completely subverted he would spread the evil to others more effectively. Thus when he was Healed in Tar Valon the "evil" in place of his soul was destroyed, leaving holes in his soul, which in turn left holes in his memories.
There are a couple of examples of this in the books, where a person had their soul destroyed and the effect it had upon them. Firstly the Ogier that had it's soul destroyed by the Machin Shin, which can be seen as the Shadow's taint equivalent to the Mashadar, a miasma of evil:
"Raving about the Machin Shin, the black wind. Aes Sedai could Heal some, but even with Aes Sedai help, they were never the same. And they never remembered anything of what had happened." (TEotW, Ch. 43)
This is the ultimate extreme for when a person loses their soul, however it must be noted that the Machin Shin also destroys the mind as, well which could be contributed to the Ogier's "blankness". Nevertheless the result of having his soul destroyed correlates with Liah the Far Dareis Mai (who is a much less extreme example) that was left behind at Shadar Logoth. After surviving in the city for about a month, she comes encounters Rand al'Thor, and barely recognizes him. Now I realize that Liah's lack of recognition could be attributed to the intense trauma of having to survive in a horror city, but when she does eventually recognize him, she runs away. I don't think this to be the workings of a sane woman.
Unlike the dagger, or a tainted item of the city, I think that when the Mashadar destroys the soul, it does not replace it with anything, it just consumes it. Now while it's unlikely that the Mashadar had caught her and then she somehow escaped it, I think that just being in the city for too long can taint a person and destroy your soul slightly, putting holes in her soul and contributing to Liah's irrationality and her lack of memory.
Now proof. Well for how long does Mat carry the dagger? A week, or perhaps two weeks? So his soul has had small parts destroyed and replaced with this "evil" which is reflected in his personality. Then when he is Healed by Moiraine in Caemlyn, he is momentarily better and says that he cannot remember what had happened. He has small holes in his soul and so his memories.
"It...ah...it seems I've been acting...ah...sort of oddly. I don't remember much of it really." (TEotW, Ch. 42)
Now of course like any sort of disease (and I'm gonna compare this with cancer for now) if even a small bit remains it will grow back. And as we can see that only the most powerful of Healing helped Mat, it is obvious that Moiraine's healing could not destroy it all.
Next, I think that the soul regenerates itself, so long as the damage isn't too extensive, similar to the body healing itself, for example a deep cut will heal, however the skin that grows back isn't the same, it's tougher and different and it's the same with the soul. The holes that have been left in Mat's soul are replaced by Mat's "previous life" (like Lews Therin is one of Rand's previous lives) souls. In effect, the same soul, but different, much as it is the same skin that grows back, but different, and as such tougher and more resistant to the Mashadar's soul-destroying effect. This is why, until Mat goes to the Eelfinn (which will be covered later) his only "new/old" memories are that of Manetheren, his birthplace and where his blood runs back. He is no doubt a direct descendant of Aemon, or at least the general that orders the "Heart Guard" and it is from this that soul pulls up more "soul". At the Eye of the World, he shouts the Manetheren battle cry and after his Healing he remembers a battle at Manetheren, so his memories, for now, are only of Mantheren. From this he knows the Old Tongue, which if we had had Birgitte around in the earlier books could have told us that his accent is only of Manetheren. The few phrases he uses before his acquiring of the dagger can be attributed to the 'old blood singing'
So the Eelfinn. When Mat asks for his "holes" to be filled, he didn't really specify which holes, although he does say "the holes in my memories, in my life". Here I think the Eelfinn fill the holes in Mat's soul, which in turn replace his memories, with the souls of generals that have entered the ter'angreal or the Tower of Ghenjei before. You see whereas the Aelfinn rummage through experience and emotions.
"sensations, emotions, experiences. They rummage through them" (TSR, Ch. 15).
I think that the Eelfinn, sample souls, rummage through them the way that the Aelfinn do. So when the Mat asks for his holes to be filled they are able to fill the holes with the snippets of soul that they have taken from these past generals that have previously entered the ter'angreal. We can see that not all of his memories are useful, he has at one point a memory of dancing in LoC.
If we can imagine that the soul holds a wealth of information, including memories, then we can presume that the souls from the Age of Legends would be more covetted by the Eelfinn. I think they filled his holes with souls that to them are worthless, memories and knowledge of people from the Trolloc Wars not being as sophisticated as those from the Age of Legends. That is the reason that Mat has memories of dancing, as well as ones of dying.
Going back to my scar tissue reference. Mat comments that he can no longer define before past memories and his own, unless he concentrates hard. This reflects in the fact that it is hard to define between scar tissue and real skin (unless it's something major anyway) and it also reflects the fact that his soul is now so closely integrated with other pieces of soul.
This also ties in with what the Aelfinn say
"and live once more a part of what was"
he is living parts of others soul that once were.
The soul holds memories. As the dagger destroys Mat's soul it replaces it with evil. When Mat is Healed the evil is destroyed leaving holes where this evil used to be. The soul can regenerate itself by taking bits of soul that has memories of a previous life. When Mat visits the Eelfinn, they fill the holes in his soul with samples of souls of those who have been in the ter'angreal before.