I was in MP in December 1985. There were lots of people there already, although you were able to wander around at your own pace. It's a wonderful place to visit (as is Cusco for that matter), and I understand photographers who want to get their own version of a shot, even if it's a "classic".
There are always alternatives. I just came back from a week at Uluru, Kata Tjuta, and Kings Canyon. It wasn't a photographic trip, but I still took a lot of shots. Some just holiday snaps for my wife and I to remember it, and some taken with "proper" photographic intent. There were lots of people taking shots of the same things (and the sunset at Uluru is pretty limited in where you can go), but in my 4th time there over the last 40 years, it's greener than I've ever seen it (6 months of unseasonal weather and about 4 times the normal rain fall), which means there were some (for me at least) really interesting things to photograph, even from the "common" sunset location.
I can understand the disappointment of missing out on a particular trip and associated photography, but the planet is shrinking as populations increase and transport becomes faster, easier, and cheaper. As always, it's about really looking if you want to find something new or different, even at an overexposed location.