The latter works fine (and offline) for me in Thunderbird. Just tried with a folder that has 7500 messages (2013 till today) and listening to the clock ticking

The latter works fine (and offline) for me in Thunderbird. Just tried with a folder that has 7500 messages (2013 till today) and listening to the clock ticking in the background: completes in exactly one second, as near as I can tell. Searching all folders at once (four big folders are 32k emails together, I don't know the total) takes ~0.3 seconds to come up with "no results", 1 second to find the only result ("umpteen" was my first guess at which query might yield a single hit :D), or 2 seconds on a generic query to find 713 results (and populate a list of 384 involved senders sorted by frequency, a timeline of volume by year, which folders those results can be found in, which mailing list it was sent to if any, etc.). This is on a then-mid-range laptop from 2018.