By moving the UE code above the validation toolkit code, the email message will always be sent regardless of whether validation passes or fails. it may have fixed the redirect issue, but I dont think it is the "correct" fix, since it basically nullifies the validation.
I would think that there was an error occurring on the page causing the header() function not to work. Probably a blank space or line between php code blocks.
Set the page back to having the UE code after the validation toolkit code and try again.
If the redirect is still not working, try adding the following to line 1, this will turn error reporting to see if a php error is causing the issue:
if there is an error, report back the text of the error and send a copy of your page.