If you're concerned about frontrunning, use http://instantdomainsearch.com. It was written by YC alum Beau Hartshorne, and I can personally vouch for his trustworthiness. We use it every batch to find new names for startups.
GoDaddy is allegedly one of the biggest domain frontrunners, so I don't see much value in instantdomainsearch.com. imo the domainsherpa.com suggestions on domain search are far superior.
That is not exactly correct. Doing a search returns data from instantdomainsearch.com itself. Only once it is returned do you have the option to go to a registrar like godaddy, among others (or just take that name to a registrar of your liking), to actually register the domain.
I have used instantdomainsearch.com many, many times myself to great success.
They are showing suggested alternative domains for sale through BuyDomains.com. It's possible they have a database of available domains, but they may also be using an API which would leak searches.
Why is it not correct ?
When I click the search button, it takes me to the GoDaddy site. Did you really try clicking the Search button on instantdomainsearch.com ?
But you do NOT need to click on the Search button at all to use the site. I used in the past and I did not even notice there was Search button.
Note that you're not guaranteed they're safe because it's trivial for an ISP to sniff all port 43 traffic, but it's a lot better than giving your unregistered name to someone who has a conflict of interest.
We are just using a linux terminal on the back end and this data goes nowhere.