I came up with a threat model where:
First of all, I am curious whether my threat model is reasonable.
Is it possible for Eve to collect a pair of $M$ and $T$, thus mounting such an attack?
Given that, is there any replay-attack-resistant MAC scheme that is widely used?
A plain MAC algorithm acts as a deterministic function of the key, message, and (maybe) a nonce. Every time you evaluate the function you get the same results. Mathematical functions do not know whether or not they're being evaluated for the first time.
Replay attack protection has to be employed at the level of the protocol. Software, not math, is necessary for this task. The maintenance of state is a necessary and critical part of the problem. (Including issues like keeping state after losing power, as well as ensuring atomicity and consistency when you have multiple endpoints or system-level concurrency.)
The best method to prevent replay attacks is to include a sequence number in the messages you're trying to create a tag for. (You might not need to explicitly send this over the network, though. That might be redundant.)
Prepend a fixed-width counter to all messages. Maintain a value n shared between the client and server. Every time a message is received, check that the message's sequence number is the value (n) which you expected. Look for n == 0 on the first message, n == 1 on the second message, and so on. If you receive a message with the correct sequence number with a valid tag then increment n. If you receive a message with an invalid tag or with a sequence value that you've already seen, then reject that message.
This method additionally protects against a man-in-the-middle's attempts to reorder or block messages. You don't want for an attacker to be able to change a message sequence ["On", "Off", "On"] to ["On", "On", "Off"]. Or to just ["Off"].
To illustrate how a sequence number solves that problem, imagine that the sender instead transmits the sequence ["1:On", "2:Off", "3:On"]. It should be obvious how repeated or reordered messages could be detected with only O(1) memory. Attempts to selectively block messages can (partly) be detected by looking for skipped sequence numbers.
(Although some protocols replace server-side checks for seq == n with seq >= n. Car key fobs, for example, might do this, since the user might be out of signal range when they press a button. If this method is employed, then it is important that all commands sent in a protocol are idempotent and that the user can tell what state the system is in. You can have "Lock" and "Unlock" commands, but not a "Toggle lock" command. For car key fob systems, a car should beep or flash its lights when locked.)
Attempts to block the last message(s) sent in a session can't be detected by looking for skipped sequence numbers, obviously. It's necessary to add a "End transmission" message (or message flag), since you can't distinguish between an incomplete session and a maliciously cut-off transmission otherwise.
A worse method to prevent replay attacks is to require the client to attach a random nonce to every MACed message. But then the server has to make more effort to track which nonces have been used. If the server sees a nonce it has already seen before, then it rejects the (replayed) message.
This kind of system lets you add idempotency to a system which wouldn't otherwise have it. This same method is used in web applications to prevent accidental doubly-posted messages. If a user has network issues, accidentally hits the refresh button, or hits the back button and resubmits a form, then the server will notice the reused nonce and ignore the re-submission.
This method does not detect reordered or selectively blocked messages. This is okay for the other accidental-double-post-detection system because blocked messages are not considered a realistic threat. Out of order posts are accepted as a "feature": The user can open two tabs, compose two messages separately, and submit the posts in whatever order they complete them in.
You could use it in other scenarios with out-of-order protocols, but it's tricky to get right. So it's not worth the risk or the extra investment in developer time.
An additional problem is that the "spent nonce" database can grow indefinitely large. A modified system could incorporate a timestamp into the nonce, allowing old records to be purged if a timestamp check is added.
You basically ONLY would opt to use this method instead of using sequence numbers if you have a powerful stateful server and low-end stateless clients. (Clients without non-volatile memory.)
Those (stateless) clients need a TRNG, because long random numbers are used to avoid accidentally reusing nonces. (Leading to false positive replay detection.)
