"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.

>>That is not exactly correct

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 ?

You are in fact correct. Typing a name and then clicking on the Search button will take you to GoDaddy.

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.

Exactly right, hence the instant part. I never noticed it either.

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.

You don't need the search button. Instantdomainsearch shows you availability on the fly, as you type each letter. That's the whole point.

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?

Same goes for www.whois.sc that links to www.cheap-registrar.com - a reseller of GoDaddy domains.

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?

If this is not a requirement of the the domain zone, it's seems like just their fraud filter got angry at your order.