>Granted, I use zsh, but I think it works pretty much the same in bash.
I also use zsh and I don't even use ctrl+r anymore. I just type a portion of the command I remember and hit the up arrow key. Almost always the command I want is only one to three arrow keys away. zsh matches partial commands really well.