Is it possible to search all users by domain?

I think you misunderstand how the access permissions work for Domain Access.

Individual uses do not have specific domain access grants. Each user has the same grants at all times. Those grants are:

-- View content assigned to 'all affiliates'
-- View content assigned to the currently active subdomain

The user accounts are tagged with subdomains only for the purpose of creating, editing, and deleting content.

You would need a separate module to change this behavior, but it is possible.

The module in question, by the way, would be very small.

You need to implement hook_domaingrants() to alter the user's grants. Something like the following:

domain_strict_domaingrants(&$grants, $account, $op) {
  if ($op == 'view') {
   $grants['domain_site'] = array();
   $grants['domain_site'] = $account['domain'];
   }
}

That hasn't been tested, but I think that is about all you would need.

http://therickards.com/api/function/hook_domaingrants/Domain

I have committed a Domain Strict module to HEAD. It enforces the behavior you describe.

It makes a nice test case for the API. Thanks.