So I have switch to another approach which works a lot better for me. I use the up and down keys for searching back and forwards in my BASH history. I have added the following to my .bash_profile:
# make bash autocomplete with up arrow
This enables me to quickly "auto complete" the commands I am typing. Although this approach has some drawbacks as well. If you have pressed the up or down key, you wont be able to further narrow your search. For me this is not a problem, since most of the time I only need to go back a few commands in the history, so a small narrowing of the suggestions are fine for my needs. But if you need to search further back in your history or not quite sure what you are actually looking for the Ctrl-r approach will probably be better for you.