Alter taxonomy autocomplete value
the simple solution to this issue, is to pass $element by reference to the first element validator:

function MYMODULE_validate(&amp;$element, &amp;$form_state) {
  (...)
  form_set_value($element, $new_value, $form_state);
  $element['#value'] = 'new_value';
}


This way, the $element['#value'] (used by the taxonomy_autocomplete_validate) can be modified and the following validators will.

The form_set_value() is not required, but since the form value has changed, it makes sense to update the state as well.

* many thanks to @ciss for helping troubleshoot the issue on #drupal and suggesting the pass by reference.