There was a topic about replacing br tags with newlines on Urban Giraffe, but it seems to have led nowhere, so I'm posting this here just so that I can find it when I again need it, and maybe of help to others too.
I modified the search_and_replace function on line 37 of models/search.php so that $this->replace is assigned a replaced string itself:
$this->replace = str_replace("\\n", ' ', $replace);
This means I want to replace any occurences of "\n"'s in my replacement string with actual newlines just prior to applying the replacement.
It's an ad hoc solution which I'm reverting once I'm done with newlines. I've not explored any possible side effects this solution may have, so use with caution.
Edit: Forum ate my br.