Since none of these orbits work it's hard to say when an impossible planet would be discovered. I'll instead go through when we could disprove the existence of a Shadow Earth. At any of these points you can alter how your universe functions to turn it from evidence against to evidence for.
In a figure eight orbit, or any other orbit that doesn't put it on the other side of the Sun, the Shadow Earth would be visible to the naked eye in the night sky, like any other classical planet, as a "wandering star". However, this orbit does not work in an Earth/Shadow-Earth/Sun system. For that system to work the three bodies must have the same mass; they're orbiting their common center of mass. It is also unstable in the n-body problem which is our Solar System.
Counter-Earths have been proposed for thousands of years, usually hidden on the other side of the Sun. Since the L3 point (the point opposite the Earth on the other side of the Sun) is not stable, especially with Venus and Mars tugging at it, this cannot exist. We know this through indirect and direct observations.
Earth's elliptical orbit also makes this configuration impossible. Since the Earth's orbit is not circular, the L3 point opposite the Sun moves around. This would make the Shadow-Earth even less stable, and it would allow it to peek out from behind the Sun twice a year. We've known orbits are elliptical since the early 1600s.
Such an object would also have its own gravitational effects on Venus and Mars and other objects in the inner solar system. These would be detectable as soon as astronomical observations were sensitive enough. For example, it was noticed that the precession of Mercury could not be explained by Newtonian gravity in 1859 which became one of the tests of general relativity. Mercury is rather hard to observe, being very small and very close to the Sun, so the changes to the orbits of Venus and Mars would be noticeable sooner.
Direct observation to refute this idea came in the 1960s when we started putting satellites in heliocentric orbits (ie. orbiting the Sun).