Is it possible for the Rho method against an Elliptic Curve to take more than the sqrt of the total state space? Is it possible for the Rho method against an Elliptic Curve to take more than the sqrt of the total state space? It the reason why this is not generally done because of a meet-in-the-middle attack?
The Rho method is probabilistic, so it's possible you could find the solution within the first few iterations, or after you've generated almost the entire space.

The probability starts getting in your favor around the square root of the order, because that's when the probability reaches approximately 50%. Since the probability increases quadratically, it's very likely to find a solution shortly after passing that point.