Unless the search form uses Javascript to build the query URL, and you have a simple <form> which submits data to a PHP script (GET or POST - doesn't matter which method), then I can think of two possible sources of this error: 1) your PHP data handling code, and 2) an Apache security module that scans/sanitizes incoming request data automatically (e.g. before it gets handed off to your PHP scripts).
Do you ever modify the $GET or $POST array (whichever is appropriate) directly? If not, have you done a [man]print_r/man on the appropriate array itself to see what the data looks like when the PHP script received it?
