perl -wle '$_="|<br />|"; s{<br />}{\par}ig; print'
Unrecognized escape \p passed through at -e line 1.
|par|
So the first solution certainly is wrong.
And I don't see how the search-and-replace could insert some weird characters - are you sure they aren't in the string before? Use hexdump or Data::Dumper to find out:
perl5.10.0 -wle '$_="!<br />!"; s{<br />}{\\par}ig; print'|hexdump -C
00000000 21 5c 70 61 72 21 0a |!\par!.|
00000007
If you are sure that the regex is misbehaving, please give us a short, executable and self-contained piece of code that demonstrates that behaviour.