AD searches are actually performed using your windows credentials, "impersonated" by the service user. AD Synchronization is the only action that might use the service user (if no other user was specified for that identity provider).

For security reasons, some directories provide the same error for "Access denied" and "No results", so when this happens, we must take our best guess.  I would expect you to get an access denied dialog with a credentials prompt if the user you are logged in to LFDS as is not able to access that domain, so I am a bit concerned if you are not getting an Access Denied dialog with an option to enter different credentials.

I cannot reproduce: when I try to search a different domain, I am correctly prompted for credentials.

If you are not getting an access denied prompt, but you know your current windows user does not have access to the domain you are searching, you may wish to open a support case as I cannot reproduce this issue.

I have an idea on how to get the credentials prompt until we can figure out why you are not seeing it, but first a note on how LFDS authenticates users:

LFDS uses the Negotiate protocol. If you are access LFDS from a machine other than the one where LFDS is installed, in order to automatically pass your windows credentials, Kerberos must be configured. This is because of the "two hop" problem, similar Web Access using automatic windows authentication. When Kerberos is not configured, LFDS falls back to a different protocol (NTLM) and prompts you to enter your credentials manually. Some browsers (e.g., Firefox) may not work out of the box with the negotiate protocol, and will prompt for credentials even when Kerberos is configured or accessing locally.

What you can try now: try accessing LFDS from a machine other than the one where it is setup (unless you have configured the SPN for the service user), or try using Firefox.