The size of the table isn’t really the issue, the queries you’re running on that table might be.
For example, if you’re selecting users based on data stored in the user-meta table, then that query will be highly unoptimized, because meta_value is not an indexed field. In which case you may need to add extra indexes or consider storing that particular data in a different manner, such as with a custom taxonomy.
Generally speaking, stuff that you store as meta should never be something that you will exclusively search based on. This applies across all the meta tables in WordPress. Meta is mainly designed to be pulled out by the meta_key, not by the meta_value. Taxonomies limit the possible values to a set and organize the information differently, so they do better when the “value” counts as what you’re selecting on.
If you like this question & answer and want to contribute, then write your question & answer and email to freewebmentor[@]gmail.com. Your question and answer will appear on FreeWebMentor.com and help other developers.