In this context, Lieutenant means second-in-command, often with respect to a particular job. The Witch-King was pretty clearly Sauron's most powerful minion, but he was usually traveling around. Sauron needed someone to command the troops of the Dark Tower itself, look after the fabric, manage logistics, and so on.
The word Lieutenant is French for "place-taker" and I'm actually a bit surprised that Tolkien called him that, because he usually avoided Romance language words for things like titles.
The Lord of the Rings states: "The Lieutenant of the Tower of Barad-dûr he was, and his name is remembered in no tale; for he himself had forgotten it, and he said: 'I am the Mouth of Sauron.' But it is told that he was a renegade, who came of the race of those that are named the Black Númenóreans ... and he entered the service of the Dark Tower when it first rose again, and because of his cunning he grew ever higher in the Lord's favour; and he learned great sorcery, and knew much of the mind of Sauron; and he was more cruel than any orc."
And that is, perhaps, a bunch of hooey. Because I strongly suspect that the Mouth of Sauron was none other than Eärnur, the long-vanished last King of Gondor. And the tale that he was a Black Númenórean nothing more than another lie in a vast tapestry of deceit woven by Sauron, the prince of lies.
The Lord of the Rings Appendix A (Annals of the Kings and Rulers) relates:
"Eärnur had held the crown only seven years when the Lord of Morgul repeated his challenge, taunting the king that to the faint heart of his youth he had now added the weakness of age. Then Mardil could no longer restrain him, and he rode with a small escort of knights to the gate of Minas Morgul.
None of that riding were ever heard of again. It was believed in Gondor that the faithless enemy had trapped the king, and that he had died in torment in Minas Morgul ...".
Possibly. But what could better please the evil genius of Sauron than capturing and twisting his enemies into slaves to do his bidding? This would be a fine imitation of Morgoth's capture, torture and corruption of elves into orcs. It is my theory that Sauron wrought a particularly gruesome example of necromancy that unnaturally prolonged the hapless Eärnur's life -- not as a wraith, but trapped in his own body.
If true, this lends particular irony to his opening verbal volley at the parley before the Black Gate with the Captains of the West:
"Is there anyone in this rout with the authority to treat with me?"
Because as the crowned king of Gondor he would have secretly held tremendous authority ... though a smidgen less than Aragorn II Elessar.
"It takes more than a king than a piece of Elvish glass." That works so well with this theory. He knows what makes a king.
Yes, exactly. I am pretty sure he is or was Earnur.