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)