Recently I have been struggling with Outlook search and I remember using Xobni few years back which has saved me on numerous occasions. Unfortunately, this last unlimited free versions seems to have completely disappeared from the web. Just wondering if anyone still has it somewhere?

Xobni has been dead for years. There is a dubious link to a x64 version of Xobni Infinity but I would not trust the source.

What I had been using for years in Outlook is Lookeen which is a pretty good search engine for Outlook and for the desktop. You can get a trial version here:
https://www.lookeen.com/index.html

FYI, in case you aren't already aware, the latest version of Outlook for Windows has a "Coming Soon" toggle in the top right which, if enabled, turns on improved search. (The improved search appears to still have a few bugs, and some of its features aren't initially obvious, but I've definitely found it to be an upgrade.)

I use NEO FInd by Caelo. Cannot recommend it enough. They have a trial, paid and subscription version.

I'll second a recommendation to try Lookeen. I have 1000's of items and Outlook's search is ok for me but Lookeen is much faster and better and has some unique features including editing in the preview pane.

OMG, if you want Outlook search and dozens of other smart features, you have to try NEO (www.emailorganizer.com). It is one of my 2 "could not live without" pieces of software. The other is X1.
Please check out NEO. I have used it as my Outlook frontend for 15 years.