> A little while back two NASA scientists published a paper on how you would detect the existence of a previous advanced society on Earth. Apparently, over a long time scale it's actually fairly difficult.

Depends on how you define advanced. Anything in geostationary orbit is basically there for the life of the solar system.