nginx reload etmemiş olabilirsin veya sürümü çok eskidir. Az önce test ettim sorunsuz olarak yönlendirdi.

Alternatif çözüm olsun diye bırakıyorum arama.php içerisine <?php den sonra

if (isset($_GET['q']) && !empty($_GET['q']) && is_string($_GET['q']) && strlen($_GET['q']) > 0 && stristr($_SERVER['REQUEST_URI'], 'arama.php')) {
    header('HTTP/1.1 301 Moved Permanently');
    if (isset($_GET['sayfa']) && !empty($_GET['sayfa']) && is_numeric($_GET['sayfa']) && $_GET['sayfa'] > 1) {
        header('Location: /arama/' . urlencode($_GET['q']) . '/sayfa/' . urlencode($_GET['sayfa']) . '/');
    } else {
        header('Location: /arama/' . urlencode($_GET['q']) . '/');
    }
    exit();
}