This is fun to think about. I've heard other people talk about plastic in the same way that speeding_snail is here. I guess the trick for plastic is that it needs to be hidden from the sun to stay intact. Plastic doesn't bio degrade, it photo degrades. All that plastic swimming in the ocean, as it swirls around in the sunlight, will basically be dissolved in a matter of decades I would imagine. This is already happening really. Once that plastic in the ocean is small enough to fit in the mouth of a fish, that's where it ends up. Speaking of plastic underground though, Geoff Manaugh has some cool things to say about abstract geology where he posits that plastics will one day be very much a part of our earth's geological layers:

Plastics, for instance, “might behave like some of the long-chain organic molecules in fossil plant twigs and branches, or the collagen in the fossilized skeletons of some marine invertebrates.” A hundred thousand Evian bottles, then, may someday transform by compression into a new quartz: vast and subterranean veins of mineralized plastic. In other words, plastics will, in fact, form a new geological layer upon the earth; plastics will be our future geology. It may take a hundred million years, but it will happen. Future Himalayan adventurers will stumble upon vast belts of plastic, compressed into ribbons between layers of bedrock. Volcanoes of the future will erupt, belching transparent magma – liquid plastic – rolling out in great sheets, boiling everything in their path. Unlucky animals will be entombed there, fossilizing slowly over another million years, till their hardened remains seem to hover inside plastic hillsides, like specimens in a resinous vitrine, an open-air museum. Future Darwins will open their sketchbooks, stunned… Fantastically, given time and the right chemical composition, underground stratigraphies of white plastic will dissolve, forming caves. Blurred and colorless stalactites will hang over subterranean lakes in which blind fish swim, unaware of the milky walls and abstract rock formations hovering all around them.

To answer your questions, I'd say maybe just 300 or so years before the casual observer finds no evidence. Depending where they are of course. I live in a city of 2.5 million, in a building over 100 years old. In this case I think it would be longer. 500?

Considering finding evidence of our existence with our current technology, I think that something traceable to us will be around forever - and be discoverable forever (barring some sort of volcanic age where everything melts). It will all be possible because of the petrification of artifact. In fact, the oldest fossil that we've discovered right now dates the original organism of its image back to 3.4 billions years ago. To discuss what might happen to our current cities this amazing article says it better than I can:

After this unceremonious burial, the petrification of our cities will start. The weight of mud and sediment will crush and distort our former homes and factories. While paper and other decomposable materials will be food for the fishes, glass, bricks and concrete have better odds of survival. Most metals will dissolve though, leaving nothing but the plastic shells of all the electronic gadgetry that we have produced. Perhaps some iron interiors will turn into pyrite. Just think of those alien palaeontologists that will be admiring your pyrite laptop interior in 100 million years!

And of all the technology we have, all that will be needed to discover your pyrite laptop is a shovel :)