Update $form based on $form_state
When a form has a validation error, the form is rebuilt from cache, meaning that the form function isn't invoked.

I could move the drupal_set_message call over to a #process or #preprocess function on the form itself or on one of the methods. These should be called again.

If the form is displayed with hook_menu you could also make a callback function which calls drupal_set_message and then fetches the form. There are a lot of ways to get around this.