I think the Control-R that readline provides just does string matching on the history. I can do Control-R ssh to find the last ssh command, or I can do Control-R blah to find the last time I used that word anywhere in a command line.

I've got a long ssh command that I use to connect to a server and set up some tunnels and I always enter it by doing Control-R and looking for part of the server's name. If it ever falls of the end of my history I'm in trouble.