The sys_ids of the record to be deleted in the sc_cat_item_user_criteria_no_mtom table in both instances must match for it to be deleted via an update set. If you've deleted the record and added it back in a non-prod instance, the sys_id will be different than it is in prod.
If you can't manually delete the record in production, then I would export the sc_cat_item_user_criteria_no_mtom record to XML from prod, import it into your subprod and then recapture the deletion in your update set.
If the sys_ids are the same, make sure there aren't preview errors preventing it from being deleted. Most often this happens when the scope of the record doesn't match the scope of the update set.
