Neeva - cofounded by an ex-Google exec also provided a paid search experience with similar features. They have since shut down and in their blog post pointed out that the issue they faced was not convincing people that they should pay for search but rather the fact that distribution of their service is difficult (i.e. being browser defaults, at work, on people's phones).
What's Kagi doing differently to be able to succeed?