Roughly how big are these files, and are they stored locally on your machine or mounted over the network (using FUSE, GVFS, or a kernel-based one like NFS?)
I've noticed a few linux file managers are quite cautious loading multimedia thumbnails for networked filesystems mounted with GVFS, not sure of a fix for that aside from looking for a command line utility to mount using FUSE instead
ffprobe is included in the ffmpeg package. For future reference you can find what package contains a file by doing dpkg-query -S /bin/ffprobe (note that the path you give it is relative to /usr)
And here are instructions from a third party explaining how to tell apt how to install them so they can be kept up to date (be sure you read the warning on the debian.org page about why they don't tell you to do that before you do it):
Depending on how exactly your file manager works, installing the codec may or may not be sufficient to display thumbnails. If not, there are probably instructions specific to your file manager for installing the appropriate plugin.
You have openh264 installed already which should cover your bases. Since it quite clearly isn't I'm not sure what to suggest. What file manager is this that's having issues?
first of all, it only searches for occurrences in already installed packages and is more or less a grep -l xxx /var/lib/dpkg/info/*.list. So you can't use it in order to determine which package to install, for that you use https://packages.debian.org or apt-file instead.
Secondly, what you search for isn't relative to anything (wtf):