解決法が下記サイト記事に載ってたので後で見返せるようにそのままメモメモ。

php5.2.17のphp-mcryptを追加。これでMagentoのインストールが進む。｜本当のWEBマーケティングを学ぶために。もっと視野を広く！確固たる自分を！
http://ameblo.jp/chamasd/entry-11166702057.html

こちらの環境で言えば、

yum install --enablerepo=utterramblings php-mcrypt-5.2.17*

/etc/rc.d/init.d/httpd restart
の2点だけでOKでした。

「yum install php-mcrypt」だけだったら「php-mcrypt5.1.*がインストール済み」ってなってしまうのでyumコマンド上では問題無く見えてしまうところがネックなんですね。

そのせいで、ずっと

って出てしまってたんよ(´・ω・｀　)