We have the exact same problem, as described below. However, to cut to the chase:
We were updating memberships by importing new membership end dates but status was never changed from expired. Finally we realized that importing an appropriate membership status (or for that matter any status that is not expired) is necessary. This produces a membership that now will be processed by the next run of the cron job and correctly categorized. Problem solved, and more importantly, problem understood!
More details below -------------
Once a membership is set to "Expired" it never seems to be examined again. We have 900 memberships, 350 of which should be either current, new or grace, but only 123 of which are currently indicated to be current, new or grace. Whenever we run the membership status rules, it only processes 123 memberships, and doesn't change any of those.
We modify membership end dates via a membership upload process and maybe that is the issue. We know that the upload won't change the status, but when we run the update membership status cron job, it does not change the status of someone whose membership end date is months or years in the future. They are still "expired", .
and seemingly, once "expired" the membership stays that way. If I use "edit" on the membership and move the end date by one day, it then is evaluated as current and all is well. Somehow the membership status rules cron job doesn't examine any memberships whose status isn't current, grace or new.
Update: Changing the order of status rules didn't change the behavior - we put the Expired rule at the top, and it still only seems to look at the 123 that were current memberships.
UPDATE - as a test: exporting four of the incorrectly labeled Expired memberships and then importing them as New, Current, Grace and Pending, we find that all four memberships have their status's changed to these four, and then running the membership status cron job changes all of these to the correct "current" status.
UPDATE 4-28-21 @petednz mentions that this answer isn't completely clear. So to clarify: updating membership end date using the membership import process requires that a membership status also be uploaded at that time. Just changing the end date to a future time does not remove the "expired" status, and the cron job doesn't apparently examine expired memberships. So importing any of the active statuses (new, current, grace, and pending) is all that is needed to make the memberships eligible for examination and categorization by the cron job. Don't upload just dates, but instead include an appropriate status.