It seems to have an annoying habit of preserving the index of the last partial match, even if you cancel it. So when you realise you were searching for the wrong substring, cancel and start over, it won't find it because you've now gone past it in the history list.

I'm still not sure of a decent solution to it (apart from using C-s to search history forward instead)

It is annoying. Generally happens to me when I "miss" the thing I was searching for and go too far. This is what I do:

    Ctrl + a, Ctrl + k (move to beginning, delete to end), Enter

Going to a new line, resets that index.

I'm sure there is a better way, but its muscle memory for me.

ctrl+c should cancel the search, saving you the line-editing workaround.

I hit the Enter key.