CHALLENGE: fix our php code please!

A few versions of WordPress ago, our custom search code was working fine:

<form method="post">
<input type="text" class="searchbox" name="apple">
<input type="submit" class="searchbox_submit" name="orange">
</form>
<?php
if (isset($_POST['orange']) && !empty($_POST['apple'])){
$term = str_replace(" ", "+", trim(strip_tags($_POST['apple'])));
header('Location: https://example.com/tag/'.$term);
}
?>

…but now it is no longer working. When a user submits a search query, the infamous “headers” WordPress error pops up like this:

Warning: Cannot modify header information - headers already sent by (output started at /home/example/public_html/wp-content/themes/example/header.php:4) in /home/example/public_html/wp-content/themes/example/header.php on line 58

Now, some of you will reply and say “check for spaces and line breaks in your php code i.e. wp-config.php and other files” but I promise you, this is not the problem. We have tried inserting this code on a fresh WordPress install with the twentyten default theme, and this error still displays whenever you try to search something.

Something must have changed in the recent WP releases, but I don’t know what, to make this custom search query not work correctly.

For the record, in the above error, “line 58” is where that custom code appears in the template, and “line 4” is usually just the opening html tag or body tag it seems.

To clarify, we are trying to make our WordPress site turn queries into this “results” format:

example.com/tag/keyword+keyword/

If anyone has any ideas why this is no longer working, or perhaps can suggest alternative coding to make this work, I would be very grateful.

Cheers all.

P.S. please note: This was previously working even with mod_security enabled on our server, and without using any special WP plugins that allow certain PHP code to execute properly… our server was using CGI as a PHP handler and is now using FCGI, for what’s its worth…