ArcGIS10.2 SDE relationship class referencing a deleted feature - how to clean up relationship class?

I am looking for a smart approach to cleaning up a relationship class, which consists of relationships that look at previously deleted objects.

To illustrate, we have db.schema.SITE (spatial), db.schema.STATUS (non-spatial) tables in our multi versioned SDE geodatabase (SQL Server), and a relationship class that relates the two tables called db.schema.SITE__STATUS. However, when I run the following query, it returns over 4000 records:

select 
ss.*, status.*, site.*
from 
db.schema.SITE__STATUS ss
left join db.schema.SITE site  on site.OBJECTID = ss.SITEID
left join db.schema.STATUS status on ss.STATUSID = status.OBJECTID 
where 
ss.statusid not in (select objectid from db.schema.STATUS)
and
ss.hubsiteid  in (select objectid from db.schema.SITE)

I suspect over time statuses have been deleted but somehow the relationship class failed to get updated. But I don’t understand (and would love to understand) how this situation is allowed to happen in the geodatabase in the first place.

One approach to cleaning up would be to remove the returned records from the relationship class using SQL, but I fear this will be filled with GOTCHAs I failed to foresee.

What would be a smart way to approach this cleaning up task?