Why on earth does this not work when all my other URL rewrites work perfectly:
rewrite "^/search/?\?q(.+)$" /search.php?q$1 break;
I did restart nginx and all of that.
Rewrite only works on uri path. You don't need to rewrite the query string part because by default it's automatically attached to the new url.
rewrite /search /search.php break;
For example, /search?q=something will be written to /search.php?q=something.
See http://wiki.nginx.org/HttpRewriteModule#rewrite for more detail. This line below addresses your question
Also rewrite operates only on path, not parameters.
search?q=whateverORsearch/?q=whatevertosearch.php?q=whatever\1instead of$1as a replacement