If it has to do with mutlisite, when WP get’s users it only gets them from the current blog. Are all the users that you’re searching for part of the current blog? Honestly, I’m not sure what all the differences are, but it has to be something specific to multisite. All I know from a quick look at WP_User_Query is that that the blog ID alters the query in several ways. This could be something you can alter using a pre_get_users filter?
