Dato che l'unico 'legame' tra DataGridView e CheckedListbox è il testo dell'item,
credo che l'unico modo è quello di iterare tra le Row del DatagridView per cercare il testo dell'item che viene deselezionato nel CheckedListbox:

se trova la corrispondenza, agisci in conseguenza.