A great deal of the land west of the Misty Mountains was old Beleriand, which was the major battlefield of the War of Wrath between the Valar and Melkor (of which Sauron was merely a lieutenant to). As far as Mordor, I believe that the way those mountains are are as old as Time, since Shelob moved there sometime in the First Age after escaping from Ungoliant (her mother)