How does Sauron rebuild his empire after losing the Ring?

Question

In the opening of the Fellowship of the Ring (film), it's depicted that essentially, the Last Alliance went to Mordor, vanquished Sauron's armies, smashed his castles, and killed him, personally (mostly anyway). He was pretty much finished.

Then jump forward 2500 years and he's back. But Gandalf also explicitly states that he has all his stuff back, too - armies, castles, etc. How did this happen without anybody noticing before now and crushing him before he's ready to fight?

It seems like a colossal mistake on the part of his enemies to just leave Mordor and forget about the whole affair. They could have set up a permanent garrison right next to Mount Doom. They could have scoured Mordor of every Orc and set up their own settlements there. They could have at least sent one bloke on horseback every year to go there and make sure he was just as dead as last year.

This question isn't about why he took so long to rebuild, or indeed, Sauron personally at all. It's entirely about his stuff. The question is why the victors of the Last Alliance didn't ensure he couldn't rebuild his armies, castles, etc.

Answer 1

Gondor did place a watch on Mordor in the Third Age; however, it began to wane during the disastrously self-indulgent reign of Atanatar, and failed entirely following the Great Plague (emphasis mine):

Atanatar Alcarin son of Hyarmendacil lived in great splendour, so that men said precious stones are pebbles in Gondor for children to play with. But Atanatar loved ease and did nothing to maintain the power that he had inherited, and his two sons were of like temper. The waning of Gondor had already begun before he died, and was doubtless observed by its enemies. The watch upon Mordor was neglected.

[...]

The second and greatest evil came upon Gondor in the reign of Telemnar, the twenty-sixth king, whose father Minardil, son of Eldacar, was slain at Pelargir by the Corsairs of Umbar. (They were led by Angamaitë and Sangahyando, the great-grandsons of Castamir.) Soon after a deadly plague came with dark winds out of the East The King and all his children died, and great numbers of the people of Gondor, especially those that lived in Osgiliath. Then for weariness and fewness of men the watch on the borders of Mordor ceased and the fortresses that guarded the passes were unmanned.

^{Return of the King Appendix A: "Annals of the Kings and Rulers" I The Númenorean Kings (iv) Gondor and the Heirs of Anárion}

This all began over a thousand years after the War of the Last Alliance (Atanatar ascended the throne in TA 1149), and nearly two thousand years before Sauron's final defeat in TA 3019.

Meanwhile, it's believed that the Nazgûl re-entered Mordor around TA 1856, two hundred years after the official end of the Great Plague, when Gondor was beset by an invasion of Wainriders:

The third evil was the invasion of the Wainriders, which sapped the waning strength of Gondor in wars that lasted for almost a hundred years. The Wainriders were a people, or a confederacy of many peoples, that came from the East; but they were stronger and better armed than any that had appeared before. They journeyed in great wains, and their chieftains fought in chariots. Stirred up, as was afterwards seen, by the emissaries of Sauron, they made a sudden assault upon Gondor, and King Narmacil II was slain in battle with them beyond Anduin in 1856. The people of eastern and southern Rhovanion were enslaved; and the frontiers of Gondor were for that time withdrawn to the Anduin and the Emyn Muil. [At this time it is thought that the Ringwraiths re-entered Mordor.]

^{Return of the King Appendix A: "Annals of the Kings and Rulers" I The Númenorean Kings (iv) Gondor and the Heirs of Anárion}

It's the Nazgûl who ultimately did much of the rebuilding; Sauron himself wouldn't return to Mordor until TA 2942:

2942 Bilbo returns to the Shire with the Ring. Sauron returns in secret to Mordor.

^{Return of the King Appendix B: "The Tale of Years" (ii) The Third Age}

Answer 2

Oh my, interesting topic indeed. I might be repeating what others have answered, but since currently I'm reading the sixth book (again, and this time in English!), I feel encouraged to join.

Sauron wasn't killed: since he's a Maiar he cannot die (not even after the destruction of the Ring). At the very least, the Elves did know this, and the Númenóreans should have also, for he was who tricked them and caused them to be the Atalantë. The Valar also knew he was returning, that's why they sent the five Istari: to guide and assist the peoples of Middle-Earth when he returned.

As others have stated, Gondor (and Arnor!) did set watch upon Mordor. Minas Ithil (later Morgul), the Tower of Cirith Ungol (where the orcs take Frodo after he's stung by Shelob), and two towers in the pass between the mountain ranges of Ephel Duath y Ered Lithui (where the black gate is located) were built by the westerners to watch over Mordor. During, like 1500 years or so, Gondor did prevent orcs and haradrim and other foul creatures from returning to Mordor. However, a set of events happened during all this time. Consider the following:

• Isildur gets killed by orcs in the Anduin.
• After Isildur's death, his only surviving son took ownership of Arnor, but didn't claim Gondor, which was instead ruled by the heirs of Isildur's brother and co-ruler, Anarion. Thus the two kingdoms were separated.
• Over time, the kings became obsessed with the lost of longevity. Over the generations, the life length passed from 400 years to 200 and less. Thus the kings dedicated time and resources to find a "cure" to long age (other than being close to Aman).
• Gondor suffered several attacks over time from several fronts: the Harad in the south and the Corsairs of Umbar in the south west, and eventually lost lots of lands there; and also from the Easterlings.
• A civil war ocurred that led to the devastation of Osgiliath and lots of people death.
• The Nazgûl created and built the northern kingdom of Angmar and constantly attacked the norther lands of Arnor, Eriador and Cardolan.
• A great plague struck Middle Earth (even killing the White Tree that Isildur had planted in memory of Anarion).
• The easterlings invaded and devastated Gondor.
• Eventually, Arnor failed and was reduced to nothing, except for the group of rangers known as the Dúnedain.
• The line of Anarion also failed, making way for the House of Stewards.

So, after the war with Sauron, Gondor/Arnor were the only beacon of light for humans in Middle Earth. After they failed, everything else decayed into some sort of Middle Ages, so to speak. It is only natural that they lost the track of things. After all, one is first concerned to bring food to the table or repel the attack from the Corsairs, before sending scouts to see if Barad-dur has been rebuilt.

However, despite this, much was done to prevent evil from returning.

• A White Council was created to counter the ever increasing eveil returning to Mordor. Saruman was tasked to learn about Sauron and prepare a defense. This happened around the same time when Déagol/Sméagol found the Ring (500+ years before the War of the Ring, and 1000+ years after the decline of Gondor started (usually considered at circa 1500 of the Third Age).
• For a long time, Arnor, Rivendell and even Mirkwood kept at bay the attacks of Angmar. Eventually, however, Angmar destroyed the last kingdom of the Dúnedain (Fornost) and Cardolan (where the Barrow-wights were sent, and from where Merry would pick a blade that eventually killed the King Witch of Angmar during the Battle of Pelennor Fields).
• The Beorlings managed to keep the pass between the Misty Mountains and Mirkwood open and orc-free for the most part.
• Rivendell and Lórien kept the orcs of Moria at bay.
• Circa 2000 of the Third Age, the last king of Gondor defeated Angmar.
• During the first 1000 years of the Third Age, or so, Gondor fought and expelled the Easterlings from Rhovanion, Mordor and the Sea of Rhûn.
• Gandalf, the chief strategist, helped the dwarves of Erebor to reclaim their kingdom, and set in motion events that would lead to the death of Smaug and the resurgence of both the dwarves of Erebor and the Iron Hills, and the Kingdom of Dale, eventually getting rid of the orcs from the north (Angmar) and Dol Guldur, which was a serious blow to Sauron (albeit he later sent easterlings to fight Dale, Mirkwood and Erebor during the War of the Ring).
• The White Council eventually drove Sauron from Mirwood. This is important. Although they were late (because of Saruman), this prevented Sauron from learning the whereabouts of the Ring.
• The Dúnedain managed to keep the borders of the Shire well protected, and managed to keep out orcs from the Barrow-wights.
• The elves managed to keep their kingdoms alive due to the power of the three rings. This is important: otherwise, the elves would have had abandoned Middle Earth for Aman long before, and maybe Aragorn wouldn't have been protected, Narsil wouldn't have been restored, Galadriel would have helped The Company, etc etc.

It's just, it wasn't enough. The westerners had to fight not only orcs, but also wicked men and Nazgûls, while at the same time watching how their kingdoms fell apart. It's not as if they forgot to fight or watch Mordor: they were overrun. Add to that Saruman's betrayal (they could have fought Sauron in Dol Goldur 100+ years before the march of Thorin Oakenshield!) and one can see why Sauron gained its former strength.