Dns resolution fails with message "dns probe possible," on "retry" connects promptly

Not using brave://settings/security?search=secure%20dns ?

If you also test by changing your DNS provider, as a test, try setting your system DNS too your ISP, and then ipconfig /flushdns via the command prompt.