If they were in the EP and you changed their status to "not in program" and then added them back into the EP, they'll go through the EP again.
Why was your case an exception?
AFAIK, the "Exhausted" computation only shows after casts, when Marketo has tried to send the content and has found none possible for a given person.
To avoid any problem, you can isolate these people into a separate, empty stream. In parallel, you can run a test with yourself or one of these leads that is an internal person.
Thank you! I appreciate the quick reply. I tested your assumption, and that is in fact correct. When adding exhausted members back into a stream they were pulled out of due to being removed from an EP, the "Exhausted" status (as a smart list constraint or for the column in the EP members' tab) only updates once the cast goes out. Until the cast occurs, the "Exhausted" status will appear as "No", which is a bit misleading, so this is good to know.