Perhaps the delete action is not accomplished right away and a column is checked. Then after a X amount of months a worker process goes around actually deleting things?
If it is needful to be able to delete stars, make a separate button for that. But it is hard to imagine such a need.
This logic should be purely in the DB model or very close to it. In any case the internal API should never ever list private repos of an organization a user isn't a member of, period. Stars or no stars. Follows or no follows. Why should it? There's no corner case here, if stars pose a problem, the problem isn't the stars, it's a defective model behind. Hiding things that aren't meant to be seen in the UI means putting business logic in the UI. Just don't.
Ideally, moving the entire serialized record to an archive table keeps things as clean as possible.