Thanks for the detailed steps. I was able to reproduce in Firefox and ended up with this cookie:
which corresponds to the Open Links in New Tab option I enabled in Step 1.
I looked through all of the network requests in the developer tools however and I didn’t see that cookie being sent to any other host, or to Brave after the search was done.
I suspect it might be a bug in Firefox where the cookie-tracking code gets confused somehow and then attributes the cookie to the wrong page.
You could file a bug with Mozilla with these reproduction steps. I don’t think the problem is on our end. This is a first-party cookie used to save your preferences. It’s not used cross-domain (it would not make any sense to do so in fact).