Bash – History Search (Ctrl+r) sometimes only allows me to search for 2 characters

First off, there is not a clean solution to your problem without reimplementing some key component of how the shell (bash in this case) deals with history. Below is a solution that maintains your local history so that the arrows work as expected. Ctrl-r in turn is bound to searching your global history. The solution depends on an excellent utility for searching through your history called hh. Below are the instructions to set everything up.

Add to a startup file either ~/.profile,~/.bash_profile or ~/.bashrc:

# Whenever a command is executed, write it to a global history
export PROMPT_COMMAND="history -a ~/.bash_history.global"

# On C-r run the swap_history_reverse.sh script, 
bind -x '"\C-r": "~/swap_history_reverse.sh"'

Create the following script ~/swap_history_reverse.sh:

#! /usr/bin/env bash

# Point hh to global history
export HISTFILE=~/.bash_history.global

# Reverse search
hh

# Restore local history
export HISTFILE=~/.bash_history 

Make the script executable:

chmod +x ~/swap_history_reverse.sh

Install hh, see INSTALL.

Once everything is in place, open up a new shell and give it a run.

Bash Reference Manual says:

Readline provides commands for searching through the command history for lines containing a specified string

You want a regexp instead of fixed string.

Try hstr:
1. Installation
2. Configuration

You should see something like this with hstr:

Update:
Another tool is fzf.

1. Install: git clone --depth 1 https://github.com/junegunn/fzf.git ~/.fzf && ~/.fzf/install

2. Re-source your ~/.bashrc: source ~/.bashrc

You should see something like this with fzf: