link() wouldn't be used in the first place if rename() were implemented atomically like it's supposed to be. Unfortunately, some implementations are broken.
This link explains in detail how maildir works. The lengths which it goes to to get reasonable semantics on top of a file system data store are quite comical. It does one very clever thing though, which is that it encodes data into the file name, forcing new renames to declare the old state as a precondition, thus preventing race conditions where something else modified the file info since it was read.