判明しました。情報元はNP_cles()のhsurさん。
http://blog.cles.jp/np_cles/item/1237
応答状況をモニターしてみると、意外なことが判明。xml形式で返ってくるべき応答が実際には一般的なhtml形式になっていたそうです。Livedoor側の実装に問題があるのかと僕は思ったのですが、その後の記述が面白いです。ソースをよく観察したところ、NP_Trackback2.0xではUserAgentを偽装していることが分かったとのこと。それで、試しに適当なUAを記述してトラックバックを打ってみたところ、あっさり成功。Livedoorのトラックバック実装は、ちゃんとそれなりの理由があってそのようになっているということも分かりました。
というわけで、必要のある人はまたまたプチ改造です。
http://kyms.ne.jp/item/46
↑
こちらの情報から最新版を確認し、該当部分を書き換えてください。