>How exactly right now you're peforming the exact phrase search?

It is a subset of the initial search, such as proposed by one or several members here recently. This was a good suggestion however. Basically, it tries to find all messages containing all the words. Then, from that dataset, I scan and only keep the one having the exact phrase, which I do with .NET code, which goes pretty fast as I am then working on the first level of result instead of the 2 millions records.