Hard links would be the simplest implementation without needing a separate database. Sure you could implement that too if you wanted to.
It would be worth checking the limits for hard links, and making sure they are suitable for a large mail system using this scheme, without having a fallback plan of some sort.
Looks like UFS hardlink limit is 32767; ext2 32000; reiser and jfs, 65535. http://www.dirvish.org/viewcvs/dirvish_1_2/FAQ.html?rev=2 see "Could linking between images be limited by a maximum link count?"
