After a nuclear apocalypse, will the earth have enough time left to go back to its pre-human state? If it did, and a new civilization appeared, would it be impossible for them to know that the initial civilization ever existed (presumably enough time has passed that space objects, etc. are gone as well)? Is is possible this happened before us?
Nuclear apocalypse that would left behind a lot of life wouldn't be able to destroy all signs of civilization. Like old mines. Holes in the ground can survive a lot, and equipment buried in them would be there to find.
There are marks of human activity on the moon, to. Flags probably got white already, but metal in the vehicles will be there a long time.
Earth crust is constantly recycled, but even with that, it seems we have about 3 billion years of fossil records available. That's a very long time. Most of the Earth's age, actually, and there are proofs that there was no oxygen earlier, so we can be pretty sure no civilization was there before.
After us? No one can resurrect species we killed. Put coal we burnt back in the ground. "Pre-human state" is impossible without miraculous technology, and nuclear holocaust is no such thing. Signs of our existence will stay, probably for billions of years. Granite funerary urns put safely in the ground, if nothing else, would reveal signs of social customs. And contrary to diamonds, buried granite is forever.
The Earth has roughly another 3 billion years before it becomes engulfed in by the sun. That is a shockingly long period of time in which a lot of decay and crustal churn can occur. While some evidence of human civilization will almost certainly exist, I think the real question is how easy it will be to find it, because evidence that exists under under 2 miles of rock, there is essentially zero chance that it will be found.
If you want to study a given era in Earth's geological history, you need to find out where rocks from that era still exist. Then you need to figure out where those rocks are not covered by hundreds of feet of other rocks, underneath a glacier, buried under soil, under hundreds of feet of lake or ocean sediment, and ideally not underneath more than a few feet of water. For example, we know nothing about the fossils on almost the entire continent of Antarctica because it's covered in ice. It could have been crawling with dinosaur cities and we would never know.
Most metals oxidize very quickly. Glass breaks and is weathered into sea glass. Plastic breaks down into tiny particles very quickly, and then will likely oxidize. Even granite, if exposed to weather will crumble over time. http://www.sepmstrata.org/page.aspx?pageid=680 Especially since, in the time it takes to evolve new sentient species (it seems to be a minimum of around 3 million years) there are guaranteed to be numerous ice ages, resulting in the soil of higher latitudes being scraped up and ground to rubble by glaciers.
Also, no offense to Molot, but I don't think mines will last very long at all. They collapse surprisingly quickly, and a lot of mining techniques intentionally collapse or fill any excavated caverns. https://en.wikipedia.org/wiki/Underground_mining_(hard_rock)#Stope_and_retreat_vs._stope_and_fill
There was a kind of cheesy TV show that dealt with this topic. https://www.youtube.com/watch?v=GyEUyqfrScU
Is it possible this happened before us?
I doubt that it is likely that advanced civilization could have developed before us. There are a lot of clues that suggest why, given that science basically says "no it didn't happen", but of course there is also a lot we cannot know for certain. So I will stop just short of saying that it is not possible at all. Obviously we have no evidience that any advanced civilization or intelligent species existed on Earth other than humans. I would also suggest that if anything advanced did develop, it did not make it into space or we would have detected it already.
This means also that I tend to disagree with your assumption that space objects would "go away" in a few million years. Perhaps they would, but it would be less likely for anything at a Legrange Point to go away that fast. Presumably one of the first things that are tried with satellites is positioning them at Legrange points, as this solves many complicated problems with only a little more effort and ingenuity. Considering that we have only been going into space for ~60 years or so, I think it's safe to assume that we have tapped the potential of the Legrange points fairly early on in our space faring age.
So on to advanced, but less advanced than us.
Firstly, mammals had an opportunity to evolve because they were small enough and successful enough in the post apocalyptic world of Earth after a massive comet impact that wiped out the dinosaurs. But are mammals the only kind of creatures that can develop high intelligence? Perhaps not. Some octopods and mollusks are quite clever. However, what creates an environment where such a species can thrive and develop culture, particularly sophisticated language? What are the advantages to such traits developing which are worth keeping? In other words when is it less important to run from predators and more important to share information? The answer would seem to be when hunting, or rather sharing the responsibility of capturing food, which benefits the group more.
I am not familiar enough with mollusks and octopods to comment on their hunting ability or collaboration skills, if any, that they possess, however...
Dolphins, which are mammals of course, do this, shepherding small snatches off of a bait ball, surrounding them with a tubular curtain of bubbles to confuse them and drive them toward the surface "cornering them", and then the dolphins take turns swimming up through the tube scooping up mouthfuls of fish. Quite an elaborate behavior. Wolves have similar tactics though, flanking, cornering (as in chasing toward water or tall grass to slow the prey) etcetera when hunting as a group.
Another interesting option, one that was explored in The Host, by Stephenie Meyer of the Twilight books and film series, is insect brains. In that case, arachnoid or spider-like. How smart can an insect be? Interesting question. To quote an article on the matter of insect intelligence, it is put forth that honey bees exhibit very intelligent behaviors. It seems dubious to me to call these behaviors intelligent as I would more easily accept that, in such a small package, such behaviors are evolved, hard-wired abilities, however I am not a neurologist nor an entomologist.
These behaviors are far above and beyond what most people would assume an insect is capable of. Without exaggerating, the honey bee is capable of advanced symbolic communication, language, facial recognition, number use, observation and mimicry, understanding of rules, and high-level problem-solving. They are, in some senses, significantly smarter than many mammals. Amazing.
But it is worth noting that insects were once very large indeed. Many millions of years ago, for which we do have a fossil record.