こんにちは。

原因が分かりました。「\n」≠LFということです。
以下に経緯を書きますが、少し長いです。

■「\n」と改行
どうやら、トリガーで指定した条件式は、データベースに保存するときに改行が「\n」（「\」と「n」の二文字）になって保存してあったようです。
mysql> select * from functions where functionid=12980;
+------------+--------+-----------+----------+--------------------+
| functionid | itemid | triggerid | function | parameter |
+------------+--------+-----------+----------+--------------------+
| 12980 | 23332 | 13522 | regexp | ".*xxx.*\n.*yyy.*" |
+------------+--------+-----------+----------+--------------------+
これはトリガーの設定ページで条件式の欄に改行そのものではなく「\n」という文字を書いたからです。

一方のデータは、改行は改行のまま保存されていました。
mysql> select * from history_str where clock=1378090084;
+--------+------------+-------------------------+-----------+
| itemid | clock | value | ns |
+--------+------------+-------------------------+-----------+
| 23332 | 1378090084 | abc xxx def
ghi yyy jkl | 258548227 |
+--------+------------+-------------------------+-----------+
zabbix_senderで送信するときは、""で囲みながら普通に改行した→改行文字が使われた、ということでしょうね。

試しに、src/libs/zbxcommon/regexp.cの、zbx_regexp()の先頭部分に
zabbix_log(LOG_LEVEL_DEBUG, "zbx_regexp: string=%s, pattern=%s", string, pattern);
という行を追加してみると、ログに
26592:20130902:121531.425 zbx_regexp: string=abc xxx def
ghi yyy jkl, pattern=.*xxx.*\n.*yyy.*
と記録されました。ここでも改行と「\n」と食い違っています。

先日書いたテストコードにも同様に↓を追加して試してみました。
printf("string=%s, pattern=%s\n", string, pattern);

char *c = zbx_regexp(str, ".*xxx.*\n.*yyy.*", &len, REG_EXTENDED | REG_NEWLINE); の場合
　string=abc xxx def
　ghi yyy jkl, pattern=.*xxx.*
　.*yyy.*
　match
　abc xxx def
　ghi yyy jkl

char *c = zbx_regexp(str, ".*xxx.*\\n.*yyy.*", &len, REG_EXTENDED | REG_NEWLINE); の場合
　string=abc xxx def
　ghi yyy jkl, pattern=.*xxx.*\n.*yyy.*
　not match

zbx_regexp()は内部でregcomp()とregexec()を呼び出して正規表現部分の処理は全てこの関数に丸投げしています。で、reg～()は「\n」を改行とみなしてくれないということですかね。

というわけで、トリガーの条件式に、「\n」ではなく改行そのものを入れてみました。
・・・しかしこれも失敗しました。

■CRLFとLF
調べてみると、どうやらトリガーの条件式の方の改行はCRLFになっているようで（ZabbixのページにはWindowsのブラウザからアクセスしている）、zabbix_senderで送った方はLFのみ。この辺が原因のようです。
というわけで、今度はfrontends/triggers.phpを見てみました。138行目辺り、
$trigger = array(
'expression' => $_REQUEST['expression'],
'description' => $_REQUEST['description'],
'priority' => $_REQUEST['priority'],
'status' => $_REQUEST['status'],
'type' => $_REQUEST['type'],
'comments' => $_REQUEST['comments'],
'url' => $_REQUEST['url'],
'dependencies' => zbx_toObject(get_request('dependencies', array()), 'triggerid')
);
POSTで受け取った値をそのまま記憶しているようです。試しに$_REQUEST['expression']をダンプして表示させてみると、やっぱりCRLFになっていました。

そこで、$_REQUEST['expression']の部分をpreg_replace("/\r\n|\r/", "\n", $_REQUEST['expression'])と書き換えてみると、改行がLFだけになり、zabbix_senderで送ったときに障害として検知されるようになりました（マルチバイトのことも考えるとmb_ereg_replace()の方がいいかも）。

■さてどうしたものか
ただ、今の挙動はバグなのか仕様なのか？本来はどうあるべきなんでしょうね。個人的には（トリガーの条件式に限らず）パラメーターを読んだ時点で改行を置換してくれると親切な気がしますが・・・。
frontends/php/include/defines.inc.phpで
$_REQUEST = $_POST + $_GET;
とありますが、ここで置換？