Whether or not there are any surviving SPQR initials inscriptions from the time of the Roman Republic is unclear. For inscriptions, the earliest use of these initials seems to have been on coins from the reign of Augustus (27 BC to 14 AD). Given the limited space on a coin compared to, for example, a public building or a monument, it would not be surprising if the short form for Senatus Populusque Romanus, SPQR, did in fact appear on coins first and only later on 'permanent stationary' objects where previously the full form had been used.
After extensive searching online and a thorough checking of Lawrence Keppie's Understanding Roman Inscriptions, the earliest SPQR initials inscription I've been able to find is on the Arch of Trajan in Benevento, built between 114 and 117 AD (see bottom right of the inscription, at the end of the text).
Image Source By Geniuss86 at Italian Wikipedia [Public domain], via Wikimedia Commons
As the OP noted, it is difficult at times to be sure what is an original inscription, especially as most images on the internet give very little information. This SPQR example with Nerva (ruled 96 to 98) looks too new to be true. The fact that Mussolini had SPQR inscribed all over Rome adds to the problem (though spotting the manhole covers is easy enough).
An earlier example of SPQR I found does not use the initials but rather the full text Senatus Populusque Romanus. This can be seen on the Arch of Titus in Rome, built around 82 AD by the emperor Domitian in honour of his brother and predecessor Titus' victories.
Image source. By Rabax63 (Diskussion) [CC BY-SA 3.0 (https://creativecommons.org/licenses/by-sa/3.0), CC BY-SA 3.0 de (https://creativecommons.org/licenses/by-sa/3.0/de/deed.en) or GFDL (http://www.gnu.org/copyleft/fdl.html)], from Wikimedia Commons
Note:
There is a map which apparently shows all the surviving SPQR inscriptions which have been discovered from the Imperial period. However, the source of this information may well be mistaken; the map may actually be showing all inscriptions (not just ones with SPQR). For the curious, a zoom version can be found here.