For now it seems that Brave is searching only Bookmarks and Typed History in the address bar and history while you did not close the browser. Probably this is a bug: I’ve not cleared history, but when I type some keywords from previous session - Brave shows just nothing.
UPDATE: I’ve found out that Chrome does the same; so this one is implementation limitation, but Vivaldi does properly search in visited page history, as does Firefox for example. This one is valuable function in my opinion: saves lots of time when you try to find some articles you’ve read, but closed the tab in some of the previous browsing sessions.
UPDATE: seems this one is bug: sometimes the function works in both Chrome/Brave. Sorry can’t really catch the pattern of it’s non working scenarios properly, but there is 100% some problem: sometimes I start typing in the addressbar and nothing but search appears.