It has happened to me previously also using BOTH namecheap/godaddy, back then I just shrugged it off, but this time it really pissed me off... So I guess the best bet is to check for domains on the ACTUAL ENTITY PROVIDER who provides domain names to resellers, such as: https://www.verisign.com/en_US/domain-names/domain-name-sear... Plus their brainstorming feature is one of the best out there IMO.
I eventually moved everything from godaddy to namecheap — I trusted them. But I’ve now had a similar experience there as well: a never-registered domain gets picked up by some Chinese entity within 24 hours of me using namecheap to check if it’s available. It took me years and hundreds of dollars to finally get that domain back.
My needs are stable for now but next domain purchase will likely be elsewhere.