form_set_error message delayed one page refresh
I had the same, here is the solution and explanation:
The key of this problem is the drupal_get_form('FOO') is called in theme layer. For example _preprocess_WHATEVER or directly in BAR.tpl.php

The messages are prepared in _process_page()  After that it's unchangeable in deeper theme functions, like FOO_preprocess_node. (That's not exactly true, but it's out of scope of this topic.)

I bet, you prepared a variable by drupal_get_form('FOO') in _preprocess_node, maybe later.

You should use hook_entity_view_alter or hook_node_view_alter, maybe hook_page_alter if necessary, anything else than theme hooks.

Just for the record: The last time you are able to set a message by drupal_set_message() is _preprocess_page