We know that the Man in Black must have a significant and meaningful name. Why else would it be deliberately concealed as it has been? Avoiding the more common suggestions (such as Aaron or Jacob), here are my speculations as to what his name might be…
Randall – A reference to Randall Flagg, the arch-villain throughout Steven King’s works, most notably The Stand, which has been one of the major literary inspirations behind Lost.
Walt (short for Walter o’Dim) – Walter o’Dim is the name of Randall Flagg in The Dark Tower series, where he is also referred to as The Man in Black. This would also be an interesting way of giving closure to the mysteries behind Walt (Michael's son) without giving worry to the actor’s age. This theory would take into account the Man in Black’s claim to Richard that Jacob stole his body. However, of my three suggestions, this is the one I believe to be most unlikely and unsatisfying.
Esau - This has always been my preferred nickname for the Man in Black. I would hope, however, that it is merely symbolic without Jacob and Esau actually being the Biblical individuals or even brothers for that matter.