Well, you do have to clarify in what form of media you want classification in. There are different qualities to classify Pokémon as legendary in both the games and the anime. I'll take a look at both.
Games: The term "legendary" is applied to those Pokémon who are at the height of the tiers. Mewtwo, Lugia, and Ho-Oh are at the top of the top. (I am not going to place Aruseus in this discussion at all, because he is god.) The other legendaries, and Slaking, are below them in terms of stats. Now, why is Slaking not counted as a legendary? Because you can get more than one. Outside of cloning, you can only get one of each legendary. (Also, outside of getting multiple copies of games, ie the beasts in Coliseum and in FR/LG.) Stats and availability are the qualities for legends in the games.
Anime: To be a legendary in the anime world, the Pokémon must have a mystical quality to it. Let's look at the example of Suicune. Its powers include controling the North Wind, and purifying water. Can any other Water type do that? No. Same with the rest of the trios - the birds, the beasts, the Regis.
So, what of Mewtwo? Mewtwo could be considered a legendary, as the people of the world that see "the dark figure that travels the skies at night" would attach stories to explain it. Thus, it could be considered a legendary at that point. Though, one must think that if Mewtwo did not destroy the palace on New Island, then the recording from its creation must still exist. It is only a matter of time before curious humans uncover that. Then, people will know the truth.
CHaRiSMa, Giovanni and Team Rocket do not know of Mewtwo anymore. Their memories were erased, due to the fact that they mistreated Mewtwo, and only want to use it for power. Ash and company are able to hold onto the memories of Mewtwo, as they befriended it, and would take its story to heart.
Black_Wind, the legend of the Beast of the Sea and the three Titans has been proven. Multiple eyewitness and secondary witnesses have seen that legend come to pass. So not all legends are unproven.
-
Excuse the long post. Legendary Pokémon fascinate me.