MAC security and adversaries with memory The usual definition of MAC security is (roughly) that there is no "efficient" adversary that has non-negligible advantage in the "MAC game" where the MAC game is as follows: the challenger chooses a random key, the adversary sends some messages to the challenger, the challenger sends the MACs of those messages with the chosen key back to adversary. For the adversary to win, the adversary now has to come up with a forged message-MAC pair. The adversary's advantage is the probability that the adversary can win the game.

Every time the adversary plays, a new key is chosen by the challenger. Does it make a difference if we allow the adversary to have a "memory" of previous plays?

For example, in round 1 of the game the challenger generates a random key $k_1$ and the adversary sends $s$ messages getting back $s$ tags, but has no idea of how to forge a MAC, losing round 1. 

In round 2, the challenger generates a new random key $k_2$, the adversary sends the same $s$ messages and, because of some weakness in the MAC algorithm and the fact that keys $k_1$ are $k_2$ are different, in round 2 the adversary can now come up with a forgery. Of course, for this to make sense, the adversary must be allowed to "remember" the results from round 1.

Maybe there are MAC algorithms that are secure against adversaries that do not remember results from round-to-round but insecure against adversaries that are allowed to have some memory.

Adversaries with this sort of memory are at least as strong as adversaries without memory. Are they strictly stronger?
Memory of the first round can't help the attacker win the second round.

If it could: the attacker could simulate the first round on his own (picking his own key, pretending to play the game against himself), and then play the second round against the challenger.

So, adversaries like this are not stronger -- not even if they have memory.