You should hook your validation code before headers are sent, like this:
function my_form_validation() {
// etc.
if ( $_POST[..] ... )
wp_redirect( ... );
// etc.
}
add_action('template_redirect', 'my_form_validation');
--
http://scribu.net