It's unlikely in the extreme. First of all, damnatio is not a systematic destruction of the identity and existence of an individual at all. It's purely the removal of the person's name from public works and destruction of public images. It's extremely important that private images and relics of the damnatus were never destroyed and were never intended to be destroyed. The precise nature of the destruction of an individual's public existence might vary (e.g. although Saturninus was probably not formally charged with damnatio, which I believe first is used of Sejanus, his images--and those of Marius--were forbidden from public display, with a penalty to anyone who did, but not actually destroyed) but it's extremely important that damnatio was purely public. There was no prohibition against maintaining a private image of the damnatus or of continuing to talk about him, which is why, after all, writers were able to continue to write about these things.

The other thing is that actually erasing the identity of an individual, publicly or otherwise, does not seem to have ever been the purpose of the damnatio. The New Pauly understands damnatio to be an extension of the idea of prohibition from the rites theoretically due to the deceased as part of the imperial cult. Certainly at the greatest time of the used of damnationes (the late 2nd and 3rd Centuries, A.D.) this seems to be true, as it does with Domitian, although damnatio occasionally was taken against lower-ranking individuals (e.g. Sejanus) although it might not formally take that name--still, even with people like Sejanus the damnatio is more or an extension of the individual's status as an enemy of the state into posterity, hence the focus on the public. Whether one was an actual emperor or not the idea of damnatio was really more ceremonial and moralistic than pragmatic--nobody thought that the entire identity of a person's existence could be systematically erased, and certainly not by only prohibiting the public memory of his deeds while leaving the private totally untouched. This also means that the scenario you offer, of a "common street thug" being targeted as a damnatus, is impossible. Damnatio was not inflicted on those of little or no political importance, ever. What public identity would a street thug have to be erased? Where are his inscriptions, his images? What could he possibly do that could warrant the extension of his status as an enemy of the state into posterity? No, damnatio is very much a punishment reserved for the very highest levels of imperial politics and administration, it's not an everyday sentence.

There's also the problem that even in the cases where damnatio was more or less successful (at least outside of literature, where the names of the damnatus are almost always preserved) we still know that something happened. It's really frigging hard to erase somebody's name from an inscription without taking down the whole damn thing, and generally inscriptions were not actually destroyed (especially if they were on buildings, which would make it unrealistic) but the names of the damnatus erased. For example, that is where Geta's name once stood. Not only is it obvious that there was a name there but we can even still make out the letters. Sometimes the erased names were actually written back in later on--that's Commodus' name, painted back in by some later authority. Sejanus' coins had their inscriptions mutilated so that his name could not be read, but it's quite obvious that there was supposed to be a name there, and we can sort of make it out even in this example. Another example of how damnatio was never intended to be subtle is the destruction of Geta's face on Caracalla's family portrait. It's patently obvious that there's supposed to be a second son there, and no effort has been made to pull a Stalin and actually doctor out anyone so that it's as if they were never there--that's not the point of damnatio.

Now, technically we wouldn't know, but for a person's actual identity to have been totally deleted from posterity is not only unlikely but very much against the whole point of the damnatio

As you say, we would be unable to prove a successful erasure from history of any person. With that out of the way, the possibility that 'major figures' could have been succesfully 'forgotten' is close to zero, and if, it is not for the reason of damnatio memoriae, but for a lack of sources.

The reasons for this are twofold. First, as you already mention, the logistics involved in such a task were tremendous. A punishment of damnatio memoriae included both the destruction of the written name and visual and plastic representations of the person. It was one of the possible consequences of a sucessful condemnation for perduellio or crimen maiestatis, essentially high treason against the Roman people. Such a sentence only made sense for famous persons in the first place, those that had the means to commit such a crime and had public images and honorary monuments of themselves that mentioned their name. So if you are such a famous person, and in the times of the Empire, the damnatio memoriae was usually used against members of the imperial family and their friends and associates - most famously Geta, but also Caligula, Iulia Livilla, Messalina, Domitian and so on - there was a lot of things to manipulate. Statues and reliefs of the imperial family were ubiquitous, and inscriptions honouring them by name even more so - for example, (almost) every Roman milestone would start with the full name and title of the current ruling emperor, and often his sons as well. That's a lot of names to erase. Same is true for e.g. Papyri, where the name would have to be erased from every letter. That would have been easy with those still in the public archives, but less so for those officials had taken home with them. Then you had the countless coins, some of which were surely hidden away in some treasury or burial. So while in theory, every publicly written instance of the name was to be erased, the actual completion of such a task was all but impossible, especially considering the extent of the empire and the necessity to control the act over such a vast territory. And in fact, there are a lot of inscriptions surviving from various persons that had been erased in other places (as you already write in your question).

Then you had the logistics of the actual execution. We know of a lot of examples where the erasion of the Name of a person that was to be punished with damnatio memoriae was only superficially erased, as is the case in this inscription of Messalina - AE 1992, 739 -, where the name is still legible, though visibly damaged. The same is true in this inscription containing the half-heartedly erased name of Geta in line three - AE 1995, 1165. In many cases, the erasures are complete, or filled in again with new text, but examples such as those above show that such a practice did never completely remove the name (and in any case, since you had to remove material from the stone, the fact that something had been removed would have been obvious, and most people would have known what originally had stood there.

For what reasons this happened we can only guess. Maybe it was sympathy with the condemned, high workload, clumsy craftsmanship, analphabetism or simply carelessness, as in the case of a bronze table from Rome, where by mistake the name of Getas uncle (who had the same name) was erased, while Geta himself remained. It seems that the actual erasing was done most diligently in those provinces with a high military presence, where the imperial decree could hope for more people willing or being ordered to carry out the act, but not every province had a considerable military presence.

Secondly, and most importantly, the practice of damnatio memoriae only considered public representation of the person in written name or in portrait. It didn't extend to the historical record or private comemmoration. This is why Livy can tell us, without a problem, about the case of M. Manlius Capitolinus, one of the earliest recorded cases (Liv. V.47, 1ff.), who had been condemned for trying to gain the kingship. And while Cassius Dio tells us that anyone even uttering or writing the name of Geta was immediately put to death (Cass. Dio LXXVIII.12, 5), he is proving himself a liar by writing about Geta using his name all the time, and Dio is writing in part during the reign of Caracalla. Historians could write about those who were punished by damnatio memoriae as much as they wished, and they did.

So then, why condemn someone to this in the first place, if it was impossible to execute anyway? That is the interesting question here, and the reason is that erasion from memory was never the goal. The goal was to manipulate remembrance of a person in a certain way (Charles Hedrick writes that 'political attacks on memory' were never an adequate measure to destroy the memory of a person; especially not with the tools available to a premodern state History and Silence (London 2000), p. 92 f.) Surely those persons who tore down the statue of Saddam Hussein during the fall of Baghdad or the statues of Lenin or Marx during the fall of the Soviet Union never for once imagined that they would be able to erase Marx, Hussein or Lenin from history. But the symbolic value of such an act is undeniable. Caracallas damnatio memoriae of Geta showed his victory over his brother and rival, his erasion from all the monuments that earlier had tried to show the strength and unity of the Severan dynasty, the concordia augustorum, with the name of Geta replaced or erased showed that Caracalla was perfectly capable of stable rule alone (well we all know how that turned out, but that's propaganda for you). Geta is a bit of a special case in that Caracalla, with a very detailed set of implementary regulations disseminated into all corners of the Empire seemed to go further than most others before or after him, to have Getas name and image (unsucessfully, one might add) removed from every corner of the Empire. But Caracalla must have known that this would be unsuccesful, and that he could not have Geta removed from all the coinage as well (which, with its 'concordia Augustorum', unity of the emperors imagery and text, would have certainly given rise to cynical observations in those comparing them with the erased names and demolished statues of the new emperors brother). Florian Krüpe has interpreted this as an act of victors revenge, and an attempt to remove any doubt about the legitimacy and stability of his rule, to which the public presence of name and image of the brother he killed himself would have been a constant threat (F. Krüpe, Die Damnatio memoriae (Mörlenbach 2011), p. 252), and I think this is quite plausible.

But in a general sense, the target of such an act was never the memory of an individual per se, but the public image and the way a person was remembered in collective memory. There is a marked difference whether someone's name and image are kept alive, honoured by statues and inscriptions in the public space, or if he only appears as a traitor, a failure, a loser, in works of history or the spoken word. After the second world war, pictures of Hitler, that had before hung in almost every house, were taken down, same as statues of the dictator, and all over Germany and Austria, Adolf-Hitler squares, plazas, avenues and streets were renamed. That doesn't mean that he will be ever forgotten, but it marks a very tangible difference in how his name is kept alive in public memory.