@PvanderValk I would try to find anything on the contact record that can be used to determine which status the lead should have - and then create a contact-based workflow that updates the associated leads accordingly.
If there is no such data point, I would consider deleting all leads, if you’re considering 90% not to be relevant - and then starting from scratch.
If neither works, I would simply go the unpleasant route of asking sales reps to update each lead in the CRM.