I use Zsh + FZF and am very happy with it. My history is about 30K entries long and it handles like a champ. I use a poor mans version of the tagging you speak

I use Zsh + FZF and am very happy with it. My history is about 30K entries long and it handles like a champ. I use a poor mans version of the tagging you speak of. I use hashtags at the end of long commands I would like to reuse. $ <long winded shell command> #restart #remote FZF history search finds them easily.