In the case of Neptune, Le Verrier hit the nail right on its head (where others suggested a limit to Newton's theory of gravity). This tremendous feat gave him all the reason to search for other perturbations around the sky to find unknown objects.
So, by 1859 he was the first to find Mercury not completely adhering to Newtonian mechanics (anomalous rate of precession of the perihelion[0]), therefore he postulated smaller unseen objects in its vicinity, even naming a possible planet Vulcan.
But there, he was wrong and Newton's law really hit a limit here at such proximity to the sun.
Ironically not at "long distances" as suggested in the anomaly of Uranus' orbit. Also, Einstein within his GR framework correctly predicted the value of deflection of "starlight passing very close to the sun" in 1915 which was validated by the measurements of Eddington taking advantage of a total eclipse in 1919 --- a natural occurring coronagraph (a big moon) of the Sun from Earth's view ;)
P.S.: I forgot to mention D'Arrest[1] role in finding Neptune in the sky:
> While still a student at the University of Berlin, d'Arrest was party to Johann Gottfried Galle's search for Neptune. On 23 September 1846, he suggested that a recently drawn chart of the sky, in the region of Urbain Le Verrier's predicted location, could be compared with the current sky to seek the displacement characteristic of a planet, as opposed to a stationary star.
[0]https://en.m.wikipedia.org/wiki/Tests_of_general_relativity#...
[1]https://en.m.wikipedia.org/wiki/Heinrich_Louis_d%27Arrest#Bi...
The follow up (correct me on the details here) is that they later measured Mercury’s orbit to a high precision, estimated that some body was disturbing Mercury’s orbit, and went looking again to repeat Sir Isaac’s miraculous math. But… nothing was there. It turned out Mercury orbits at relativistic speeds and Newton’s model wasn’t taking that into account.
Vaguely remember this from Kuhn’s Structure of Scientific Revolutions