It’s definitely a server level redirect. Do you have access to the .htaccess file on the server? What does that look like, maybe there is something in it that’s detecting something in the submission and attempting to redirect, but that would be extremely odd. If you have access to it can you post the content of any .htaccess files?
I did find this, but I don’t know if it’s any help. http://wordpress.stackexchange.com/questions/77337/page-returns-404-with-post-variables-but-not-without.
Finally, what is the exact page url that you end up on that shows the 404?
