As many other comments have suggested, orbit altitude is a key parameter in determining how visible the recon satellite would be. However, orbital altitude also determines how long the object will stay in orbit—specifically the perigee (lowest-point) altitude.
Let's say the recon satellite was in a roughly-circular¹ orbit of 400km, which is approximately the orbit of the International Space Station. Let's also assume that the recon satellite was shaped like a white school bus. This would would make it much more dim than what the ISS would be (ISS is huge!), but I think should occasionally be visible in the night sky when it is broadside. Ultimately I think it would be noticed, but, due to atmospheric drag, it would deorbit within a year or two. You could, of course, use thrusters to maintain your orbit, but eventually the fuel will run out. The most amount of time you could expect it to maintain such a low orbit would be on the order of a decade or two, and even that is pushing modern technology².
If you doubled the perigee to, say, 800km, you've given yourself about 100 years if the orbit is somewhat circular. The recon satellite would be just 1/4th as bright when directly overhead, making it significantly more difficult to notice. But, as the orbit decays, it would slowly start to become more visible until everyone would notice. And then plop, it would suddenly disappear as it drops into ocean somewhere out of human view.
Past a perigee of 800km, the time your recon satellite stays in orbit dramatically increases. At a 1000km roughly-circular orbit, you are talking around a thousand years. If the eccentricity of the orbit is high, then it could be in orbit for several thousand years.
Geosynchronous orbit is around 35,780km. Those birds are going to be practically eternal, lasting for eons. However, they would likely be invisible to any society without early 20th century optics: being 8000 times less bright than at 400km.
While I really have no idea when a society might realize that it was not a natural satellite, if I had to guess I would say it would require something on the order of mid-20th-century optics. This answer shows a great example of the kind of image of an object at 400km with a 0.64m telescope. You can see a picture of the space shuttle in that picture, so you can use that for scale: a school bus could easily fit in the cargo bay.
Anything at a geosynchronous orbit would likely remain unnoticed or of little interest until the 1960's, when it would eventually be detected using radar and catalogued. It would at first be assumed to be natural, but eventually scientists would likely want to examine it more closely (late 1970's?), and then the jig would be up.
¹ My understanding is that modern spy satellites often have highly eccentric orbits with perigee altitudes of 250km-600km.
² There is little chance that any orbital machine built using 21st century techniques would remain functional in any capacity past 100 years without maintenance. Space is a very harsh and unforgiving environment.