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.
Typing in a domain name and clicking "search" on instantdomainsearch.com immediately takes you to the GoDaddy website which shows the domain name you typed in and quotes a price for it.
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.
"Typing in a domain name and clicking "search" on instantdomainsearch.com immediately takes you to the GoDaddy"
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.
By reading their FAQ it appears that they use DNS NS records (not WHOIS) to check whether a domain is registered or not. That's relatively safe from leaking.
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.
The autocomplete shows data that seems to be from instantdomainsearch, but clicking the search button or pressing <enter> opens a new window with a GoDaddy page. Unexpected and undesirable.
Perhaps only the 'instant' part of the search -- covering only exact matches ending in .com/.net/.org -- is private, and GoDaddy is used for a more general search?
I just bought a domain through said service and today received an email asking me to scan a copy of my passport or similar, or they may cancel the order. Is this common practice?
It's not hard to launch terminal and type whois <domain>. Just do it and have a much higher likelihood that your new names and business concepts are safe.
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.
If I recall correctly Instant Domain Search is using DNS queries to quickly check availability (which can yield false positives, BTW). Hopefully he's also using a trustworthy name server...