I would say space debris would be your best shot.
I would imagine that any matter put into orbit 2 billion would still be present in some format, whether it be dust or debris. I'm not too sure on the rate of decay for metals/plastics in space, but I'd assume most things would get smashed up beyond recognition by various collisions over the years. However, some chunks of various satellites or rockets may remain.
If you're talking super-advanced Civ though, you could always develop a super-alloy that can stand up to just about anything?
EDIT: It seems Joe has directly contradicted my ideas - he's probably right, I hadn't thought of orbital decay