Ctrl+R gives you reverse i-search of bash history, however, once you have selected a command to edit (by hitting ESC) the next search would start from the same line, because it's incremental by definition.
This is useful but sometimes you wanna start over. You can rewind/fast-forward your search position in history by:
M-> # move to the latest entry M-< # move to the earliest entry
You can also do forward incremental search by Ctrl+S. But unfortunately in bash on most distributions Ctrl+S is assigned to "Stop".
Check what the meta commands are assigned to by
If you see
ixon, you need to turn it off by