Recommendations from within Ask Ubuntu

From this (Clipboard Manager for Ubuntu 16.04) we learn from users:

• Clipit is the best among all.
• CopyQ is a cross-platform, well-designed and fully-featured clipboard manager (my favorite). It features among others a (very handy) command line interface.

From this (Ubuntu 14.04 Clipboard Manager?) we learn from users:

• Glipper is a clipboard manager, it can be installed from the Software Center.
• I use ClipIt is a Parcelite fork with Ubuntu menu integration. (This package was listed in first section above)
• I’m using GPaste
• You can try Keepboard. It is easy to use and seems to be stable and reliable.
• Diodon is another good option available for both GTK and Unity. Works pretty much like the others in the answers already given. However, you can search your recent ‘clips’ using Dash. (You are already using this version though and don’t like it.)
• I use Clippy, a docklet that works with Plank (I don’t use Unity). I think Clippy also comes with Docky.

Recommendations outside of Ask Ubuntu

Not to be outdone by Ubuntu users this (tecmint.com - 10 best clipboard managers for Linux) recommends:

• CopyQ is an advanced clipboard manager which is available on most if not all platforms.
• GPaste is a powerful and great clipboard manager for GNOME based distributions, but can work on a variety of desktop environments as well
• Diodon is a light weight but yet powerful clipboard manager designed to work best when integrated with Unity and GNOME desktop environments. (Once again you do not like this package)
• Pastie is a simple clipboard manager for Ubuntu and makes use of the AppIndicator. It has some cool features.
• Parcellite is a stripped down, lightweight GTK+2, basic-features clipboard manager for Linux.
• Glipper is a clipboard management tool for GNOME desktop environment, users can extend its functionality using plugins. It now uses the App Indicator to support Unity and Gnome Classic desktop environments in Ubuntu.
• Clipit is a lightweight GTK+ clipboard manager. It is feature rich and actually forked from Parcellite, but includes some extra features and bug fixes.
• Keepboard is a cross-platform clipboard manager that allows users to save clipboard history.
• I’ve removed some from the list those that do not work with Ubuntu. So it doesn’t add up to 10 in the article title.

There are other reviews of the same packages listed above found in (makeuseof.com - 6 Tools to manage Linux clipboard) and in (maketecheasier.com - Enhance Linux clipboard with clipboard manager).

Summary

At the end of the day the package you choose is the one that you are most comfortable with. No one can say for sure which package that will be. Almost all of them offer searchable history like you want it but which one has the interface best attuned to your way of thinking?