明日とか言いつつ、時間たっちゃったな。
てことで xz-utils 5.1.1alpha+20120614 で確認してみた。
なんで 5.0.4じゃないかというと、debian sid に 5.0.4 がなかったから。

試した結果だけど、若干前よりどちらも圧縮率は上がったけど、
圧縮率の差はそのまま。
>>73 の 5.0.3のliblzma fixesは関係なかったみたい。

$ ls -al logs_with*tar*
-rw-r--r-- 1 hiro hiro 16920 2013-01-14 03:54 logs_with_dir.tar.xz
-rw-r--r-- 1 hiro hiro 13836 2013-01-14 03:55 logs_without_dir.tar.xz
$ xz -l logs_with*dir.tar.xz
Strms Blocks Compressed Uncompressed Ratio Check Filename
1 1 16.5 KiB 46.4 MiB 0.000 CRC64 logs_with_dir.tar.xz
1 1 13.5 KiB 46.4 MiB 0.000 CRC64 logs_without_dir.tar.xz
-------------------------------------------------------------------------------
2 2 30.0 KiB 92.8 MiB 0.000 CRC64 2 files

>>67の人が検証してくれたおかげでとりあえず確認できたのは、
どうやらメモリ環境によって圧縮率は変動するらしいってことくらいか。
確かにそれらしいことが xz の man pageの "Memory usage"に
書かれてるけど、ディレクトリありなしによって圧縮率が変動する
ことの理由にはなってないよなぁ。

てことで、なんかすっきりしないけど、解明はあきらめました。
>>67の人は協力してくれてありがとう。
誰かが xz-utilsのソース読み込んで、
この現象をすっきり説明してくれることを願う。