Obviously the famous tria nomina such as Gaius Julius Caesar 'styled' Romans fell out of use during in the imperial period. I know Boethius (d. 524) traces his genealogy back to the Anicii of Rome (Anicius Manlius Severinus Boethius), but I was wondering how far into the Middle Ages did the tria nomina of prominent or really any Roman descendants stay in use? Can any noble Italian families trace their surnames back that far? What about provincials such as Frankish, Spanish, etc?
We can't really tell for sure, but Quintus Aurelius Memmius Symmachus who died in 526, grandson of the famous 'last true Roman' Quintus Aurelius Symmachus, would be a good bet for that position, and is often cited as the latest reliable example for someone using the classical naming formular. But generally, as you say, the conventional naming system broke down due to a variety of factors already beginning in the 1st century BC, until in the 5th century Roman (and by extension, European) naming conventions had largely reverted back to a single name system. Symmachus was a traditional aristocrat, which is the main reason he was still using that kind of name, but he is an outlier at the extreme end.
I go into a bit more of detail into the factors in these threads:
https://www.reddit.com/r/AskHistorians/comments/3xtjlr/have_any_roman_surnames_survived_into_modern/
https://www.reddit.com/r/AskHistorians/comments/46sepg/roman_names/
See also this great summary by /u/bitparity on the socioeconomic background of the whole matter. But feel free to ask additional questions for clarification :)