The "questionable" bots might be me. I usually play on a faster speed.
Good on ya!
At what stage would the maps be impossible to finish?
This is hard to say, currently. The work curve calculations were done on "scaled down" difficulty maps, and includes a probabilistic analysis over extremely low TT solutions. It is hard to say what low TT solutions on a full map will actually look like until we get there under the new configuration. Other factors such as the combination of path-finding times and potential warp corrections could complicate the question.
You mentioned that increasing the difficulty if the bots start taking over again or if it is too easy. What would change?
To start, we could just increase the static path length requirement. This basically gives us something of an inflection point on our whole curve, allowing us to move the "exponential portion" of the logistic curve either direction along the horizontal (TT) axis. By changing base work requirements (such as hashing rounds required in map generation) we can affect both the base and slope (really, growth rate) of the exponential portion of the curve, as well. This gives us the ability to "shape" our work function requirements to network conditions over time. (In theory, this could eventually be automated within protocol itself.)
Our goal is basically to never again allow the work curve to pragmatically "become shaped like" a full logistic S curve. As long as it continues to be shaped such that play is only allowed within the exponential growth portion of the curve, we are fine. If the "leveling off" of the work at low TT presents itself again, and the average work curve pragmatically shows as an S curve again, the challenge will need to be further hardened as the network would then again be at risk of a warp attack.
I hope to find some time to put together some animated graphs to illustrate this whole mess, and how "bad" it actually got.
A very simply way to think of it is like this: If you can quickly solve an ~8.7 second straight line solution, what is the work difference between a TT of 60 seconds, 30 seconds, 15 seconds, or ~8.7 seconds? Answer: virtually none. Once you get to a "perfect solver" for unconstrained maps the logistic curve has "flattened" so that the exponential portion is basically all the way at the left (small differences in the start of the map, etc, make it never "practically vertical" entirely) and work over your range of TTs flat-lines - it is all the same work required at any difficulty.
We actually got there.
More polygons? Less straight paths?
Less straight paths. Even just removing one bit (50%) out of the available map nonce space seems to have made a significant improvement in balancing mining! (None of the nonce values I've seen have been very large... "big" nonces are now back in the tens.) There's a small performance trade-off, here, but I think it can easily be managed with simple mechanisms like background map work, as WilliamLie mentioned.