I’m afraid so, since there is already a Discourse(Rails) route named /search: it hits the SearchController before it can be processed by the PermalinkController.
The .php part is considered (mistaken) as the desired response format, thus the 406.
There could be better solutions, but I think you’ll have to handle the redirect on NGINX, before it gets to Discourse:
Maybe something along the lines of: (not tested)
location = /search.php {
return 301 /search?$args;
}