Thanks again for your detailed comments!

Here is the new patch.  As you will see, it is possible to put nil in the 
cdr of the symbol property, in which case the search direction does not 
change, but I would not recommend to do that: I tried it, and the 
resulting behavior is not what one would expect, very often the match 
doesn't change at all.  Therefore I did not mention that possibility in 
the manual.

Also, there's a condition-case around the funcall, to catch beginning of 
buffer / end of buffer errors.