For public-key crypto, the server keeps a public list of mappings from user names to the users' public keys, with each mapping signed by the server. In this case, only the mechanism to add new users to the list needs to be secured, but that can even happen offline. This is covered in more detail in another paper. In an interactive protocol, these can just be random numbers, sent and verified by each party. In a non-interactive protocol, a value tends to be used that is somehow based on the time.
Users keep track of the timestamps they receive, and ignore duplicates.
Sufficiently old timestamps are thrown away.