FAPI #required and hook_form_validate ?
This behaviour is usually caused by the form being rendered too late in the page build process (for example by calling echo render(drupal_get_form('form_id')); directly in a template file). 

By the time the form submits, the session messages have already been prepared for rendering, and so when more messages are added by your form's validation, they don't display until the next page load.

Without knowing exactly where you're rendering/preparing the form is hard to offer advice on how to fix it. I think it would suffice to say that if you're rendering the form directly in a template file, you should move it to a preprocess function at least.

The better way would be to prepare and render the form at the module level, rather than the theme level, as that will be processed early enough in the page load for this problem to disappear.

To address your comment:

I think the problem is definitely where you're calling the form building function from. You should be able to just take that code and put in a preprocess function, preferably in a module file as that pretty much guarantees the call won't come too late:

function MYMODULE_preprocess_page(&amp;$vars) {
  if ($_GET['q'] == 'some/path') {
    $vars['the_form'] = module_invoke('my_module', 'block_view', 0);
  }
}


Then just print it if it's available in page.tpl.php:

&lt;?php if ($the_form): echo $the_form; endif; ?&gt;