Perhaps adding a UUID is too much overhead? If you have a very high throughput system with messages of less than 128 bits, then the addition of a UUID to every message would effectively cut throughput in half.
I do not have such a use case in mind, but the description above does not sound terribly unrealistic to me.
Also in order to track UUIDs that have been received, you would either need an infinite amount of memory, or have the system bounded in terms of how many messages out of order a message be delivered and still be processed correctly.
You can use a database. Practically, most systems will keep a record of each message on disk in any case (at least they will have some logs) so it's not that outrageous. Safe to assume that the receiver can discard non-authenticated messages to avoid spam.
I do not have such a use case in mind, but the description above does not sound terribly unrealistic to me.