All I know is in emacs, let's say we did ^Rgrandma this morning, and in the afternoon we did ^Rgrandpa.
Well we could do ^R^R to search for grandpa again, and for grandma we could employ ^R then > M-p (translated from <escape> p) runs the command > previous-history-element (found in minibuffer-local-isearch-map), so maybe readline could benefit from something like that. Also see emacs' next-history-element. Of course the name would need to be changed to previous-search or something.
