Rules: Load List of Entities by Object or Entity ID (Performance)
Using Solution A will pretty sure have performance implications, so I wouldn't recommend that approach "to load hundreds or thousands of Users". Below is a blueprint of yet another approach (another option that you could considered, up to you to decide if it is "better"), which will allow you to reduce the performance risk significantly ...

Step 1 - Refine your view

Adapt the VBO view you already have, by limiting the results of that view to the first X users only. Pick a value for X that fits your needs, to start make it small enough and increase later on as much as you feel comfortable with.

Also adapt the views filter, to no longer include the users that have been processed already (by the Rules Component described in the next steps).

Step 2 - Create a Rules Component

Create a custom Rules Component which performs the Rules Actions as in your Solution "B" or "C". If the value of X is small enough, you can do some experiments with either of these solutions (B or C), i.e. to find out what happens if you increase the value of X (and based on that decide for yourself which one works best). Note that the list to be processed is limited to "X users" only (i.e. those that are contained in your views results from the previous step).

Add an additional Rules Action in your Rules Component, to actually reschedule the execution of this Rules Component itself after a few seconds or minutes (whatever fits). And trigger the very first execution of this Rules Component via a custom rule that is triggered "When any user of a Company purchases membership" (as in your question, I bet you have some appropriate Rules Event for that).

Step 3 - Stop rescheduling the Rules Component when the time is right

Also add a Rules Condition in the Rules Component of the previous step, to "Check the number of results returned by a VBO view" (using the same VBO view). The actual number of results should be at least 1. If there are zero results, then the Rules Actions of this Rules Component will not be performed, which is what we want. Since it will also prevent the the rules component reschedules itself when all users have been processed.

Step 4 - Review the frequency of your cron jobs

Make sure your cron job runs frequent enough, because each execution of your scheduled Rules Component will actually only happen when cron runs.

Conclusion: because this approach is based on the Rules Scheduler, the elapsed time will be longer, for sure. But the advantage of it is that, as compared to any of your 3 solutions as in your question, the poor user "of the Company who purchased the membership", will not have to wait for the rule to complete execution, before being able to do anything else on the site.

PS: I'm assuming this is about D7 ...