Я только что столкнулся с этой проблемой и не нашел много в Google, кроме вопроса SO, на который ссылается Тим. Это звучит как большая работа для такой основной потребности, которая является для меня красным флагом. Поэтому я думаю, что проблема заключается в дизайне.
В моем случае я очень просто решил это, используя ListView
вместо CheckedListBox
(изменение его свойств позволяет действительно получить поведение CheckedListBox
в противном случае).