Checking for required on Zend_Form_Element_Checkbox using notEmpty does not make any sense, in my opinion. "Required" for a checkbox should be defined as the fact that the checkbox was checked; Not that the value is not empty. Here is the solution I am currently using in an extended class of my own:

    class ZendExt_Form_Element_Checkbox extends Zend_Form_Element_Checkbox
    {
        //...
        public function isValid($value, $context = null)
        {
            $this->setValue($value);

            if ($this->isRequired() && !$this->isChecked())
            {
                $translator      = $this->getTranslator();
                $this->addError($translator->translate('checkboxRequired'));
                return false;
            }
            
            return parent::isValid($value, $context);
        }
        //...
   }