When, in a subclass of Zend_Form, a Zend_Form_Element is setRequired(true) it automatically adds a NotEmpty validator using the default message. To override the default message add a NotEmpty validator at the top of the list of validators and set breakChainOnFailure to true.

$username = new Zend_Form_Element_Text('username');
$username->setLabel('Username')
->setRequired(true)
->addFilter('StripTags')
->addFilter('StringTrim')
->addValidator('NotEmpty', true, array(
     'messages' => array(
          'isEmpty' => 'Username is required'
     )
  ))
->addValidator('Alnum', false, array(
     'messages' => array(
          'notAlnum' => 'Use only letters and numbers'
     )
  ));

The solution, given by Matthew Weier O’Phinney,  was found in the following thread:

Form Validation Messages

Related threads:

how to set error message for Required form validator?

Using Zend Framework and setting a Zend_Form_Element form field to be required, how do I change the validator used to ensure that the element is not blank

Zend_Form_Element NotEmpy validation when required is set to true

The validation failure message keys, i.e. isEmpty, notAlnum, can be found in the API Docs or by directly reading the validation class file in the library/Zend/Validate folder.