Indus Valley (IV) Civilization is supposed to be very old and there are no relics giving us any inkling about the religious beliefs and practices of the people in those days. The rigveda also does not give any indication about the IV people in any form. However, experts - even Indian experts - agree that the Pasupati and Rudra seals ( so named because of the closeness of the figures in these two seals) may represent the kind of god-belief which those people might have had.
Rigveda mentions vishnu, of course. But it is for everyone to see that the vishnu of the rigveda was a minor deva, subservient to the almighty Indra and most scholars agree that the rigvedic vishnu is no more than a sidekick for Indra, at best. I may add that in Satapatha Braahmana I.2.5.1, Devas fought asuras and the asuras defeated the devas. Hence the devas had to beg the asuras for a piece of land to live on. And the braahmana text continues in this way:—
"Now, vishnu was a dwarf. The Devas, however, were not offended at this, but said : much indeed they gave us, who gave us what is equal in size to the sacrifice.
Having then laid him (i.e., vishnu) eastwards, they enclosed him on all three sides with the metres, saying (Vaajasaneya Samhita I.27), on the south side, "with gaayatree metre I enclose thee!"; on the west side, "with the Trishtubh metre I enclose thee!": on the north side, "with the jagatee metre I enclose thee!".
Having thus enclosed him on all three sides, and having placed Agni on the east side, they went on worshipping and toiling with it (or, him, vishnu, the object of sacrifice). By it they obtained this entire earth and because they obtained this entire (earth), therefore it (the sacrificial ground) is called vEdi (the altar). ...and so on the story goes.
It should be clear from the above that vishnu was, after all, a spareable entity even for the Devas, which (who) could even be sacrificed in order to get some piece of land from the victorious asuras.
Hence it will not hold water to say that vishnu had become a "worshipped" entity even beyond the times of Vedas.
The vasudeva cult, the bhagavata cult, etc., were beliefs among some sections of the people living in the sub-continent and these could be no more than tribal beliefs which had begun to take the shape of cults. For example, the vasudeva cult had it that vasudeva -krishna was the brother of Samkarshana-Baladeva and that Vasudeva defeated his maternal uncle Kamsa in a fight and killed the latter. Kamsavadha was enacted as pantomimic drama in Patanjali's times and the people formed into two groups vasudevabhaktas and kamsabhaktas, the former overcoming the latter eventually as the drama closed. Having said in so much detail in his Mahabhashya (dated to 2nd. century BCE), Patanjali does not say that this vasudeva - krishna was vishnu, or was identified with vishnu.
The vishnu cult became popular during the Guptas' times most possibly and, in course of time, the three cults (Bhagavata, vasudeva-krishna and vishnu) merged to form what came to be known as Vaishnavam or Vaishnavism. Since most of the puranas also took shape during the reign of the Guptas (which came some time after the Sunga dynasty, and more as a rebellion against oppressive rulers), it was but natural that the newly formed vishnu cult got more than one purana/scripture to support its ancient origins etc.