If you have two "Samulis" in the system, and one in the selected role, then searching for "Samuli" will show "Search results (2)" but only one "Samuli" on the list.
The problem code is in /admin/roles/assign.php and assign.html. It counts the number of search hits before subtracting the $contextusers that are already in the context.
The problem is more in-your-face if all of the search results are alredy in the context. You get a non-zero amount of search results, but an empty list nevertheless.
One possible solution: use the get_users() instead, and construct the exceptions-list for the function call, based on $contextusers.