I found a solution to my problem. I named the checkboxes when I created them with a unique name pattern, then deleted all the checkboxes with that name pattern.
                With shCompare
                    For i = 1 To iMatches
                        Set ck = Nothing
                        On Error Resume Next
                        Set ck = .CheckBoxes("Match " & i)
                        On Error GoTo HE
                        If Not ck Is Nothing Then
                            ck.Delete
                        End If
                    Next i
                End With
I'm still interested in finding out why my first code doesn't work.