I believe that Mat's memories come from many different sources also, and not just randomly, but to serve him at the particular time he needs them. Similar to Rand's ability to remember different flows at the time he needs them, though he has never done them in this present life. I also believe that Mat's "choice" of weapon is a big clue to his past. The fact that he is quite adept at the staff with the blade, bringing the blade into play as if he had done it before, rules out Gaidal Cain, I believe. If he were Gaidal Cain, I believe he would have shown more interest and ability in swords. (Side note: Possibly Galad or Gawyn is Gaidal Cain, assuming anybody could be, since Gaidal Cain showed up at the sounding of the Horn). I can not say that I can place where the staff with blade combo could take us as a clue, since I can not think of any mention of a particular nation that favored such a weapon, but I do not believe the Foxes gave him that weapon by happenstance. Just !a thought...