At what date did the Ostrogoths formally stop ruling as Roman tributaries?

The Wikipedia article on the Gothic War explains a lot of the situation revolving around the status of Italy under the Goths and the reason the Eastern Roman Empire decided to invade. As I understand the issue, Odoacer legalized his position as you said by acting as a vassal of the Eastern Roman Emperor. But Zeno was mistrustful of Odoacer and sent Theodoric as a representative of the Empire to restore order in Italy. After his success he took up the roles of viceroy and head of the army which consisted from Goths now. Theoderic tried to retain the agreement he made with Zeno and Anastasius. From the Wikipedia article mentioned above:

In the arrangement between Theodoric and Zeno, and his successor Anastasius, the land and its people were regarded as part of the Empire, with Theodoric a viceroy and head of the army (magister militum).[1] This arrangement was scrupulously observed by Theodoric; there was continuity in civil administration, which was staffed exclusively by Romans, and legislation remained the preserve of the Emperor.[2] The army, on the other hand, was exclusively Gothic, under the authority of their chiefs and courts.

So for all intents and purposes Theoderic was indeed acting under direct orders from the Emperor and had more legitimacy than Odoacer. However during Justin I's reign the situation in Italy was ripe to bring Italy to the fold. And the situation in Italy was such that removed legitimacy from the Ostrogothic regime:

Theodoric was succeeded by his infant grandson Athalaric in August 526, with his mother, Amalasuntha, as regent; she had received a Roman education and began a rapprochement with the Senate and the Empire. This conciliation and Athalaric's Roman education displeased Gothic magnates, who plotted against her. Amalasuntha had three of the leading conspirators killed and wrote to the new Emperor, Justinian I, asking for sanctuary if she was deposed. Amalasuntha remained in Italy.[6]

These plots and Amalasuntha's plea for help gave the pretext Justin needed to order Belissarius to invade Italy and restore order much as Theoderic had done before. So to give a definite answer to your question, the fiction was retained during the entire Ostrogothic rule, it stopped being a fiction with the brief reconquest of Italy from the Eastern Roman Empire but this success was shortlived and ended abruptly with the Lombard invasion.

"Pretense" and "Fiction" are certainly the right words for it. Nobody really bought into it at the time (except the Roman Senate, at knife-point), and I wouldn't suggest we do so now.

The ruler of the Eastern Roman Empire Zeno made it clear he felt Julius Nepos was the rightful ruler of the West until his death in 480. He didn't accept Odacter or his puppet Western Emperor, but there wasn't anything he could do about them immediately. Eastern resources were fairly well consumed keeping their own borders guarded and bribing their own German tribes.

As far as the Eastern Empire was concerned, Julius Nepos was the Western Emperor from 474 to 480 (although for the last 5 years, he only actually controlled a bit of Dalmatia), and after that, there never was another one. Odacter was never really accepted by them as anything but a fait accompli, and Theodoric's status entirely relied on the fact that he initially invaded Italy with Eastern Emperor Zeno's encouragement.

There was really only one Ostrogothic ruler after that^*, Theodoric's grandson Athalaric. His death in 534 set off a chain of events that saw the Ostrogothic kingdom at war with The Eastern Empire the next year, which ended with Rome (re?)taken for Emperor Justinian.

^{* - OK, technically there were three more, but they all spent their entire rule losing their territory to the armies of the Eastern Roman Emperors}