Извиняюсь, проблема решена. Для тех кто вдруг наткнулся.
До этого момента я со строкой $message поглумился этой функцией
mysql_real_escape_string — она заменяет все специальные символы, включая переносы строк. Поэтому невозможно найти их потом. Надо их искать как \\r и \\n.
Проблема в том, что я реально сдуплил с тем, что а XDEBUG все равно показывал \r\n а они там уже были в виде символов, а не в виде специальных символов.