hai provato cosi:
codice:
    str_replace("
\n
","</p>

",$messaggio);
oppure:
codice:
    str_replace("
\r\n
","</p>

",$messaggio);