所有者に辿り着けない土地の木に対して受けた被害を請求したい。

隣の土地に生えている木の管理が悪く、私の所有している借家に数十年に渡り様々な迷惑を被っている。

落ち葉(屋根の雨樋詰まり)、アンテナや屋根(雨漏り50万円)の破壊、枝が垂れ込めて周囲からの視界を遮り治安の悪化(ガラス被害、ゴミ、盗難自転車の放置)

相手の登記簿を確認したが情報が古く連絡先がわからない。

修繕費・慰謝料・迷惑料の請求は可能か?
相手を特定する調査費用、民事訴訟を起こした場合の弁護士を雇う費用はどのくらいかかるか知りたい。

まず現在の所有者を特定するために、登記簿の所有者の戸籍をたどっていって相続人を見つけるという作業が必要になるでしょう。
個人ではできないので、弁護士に依頼することを勧めます。費用はいくら請求するかによっても異なるので、ここではお答えできません。
直接お近くの法律事務所で相談の際に聞くことを勧めます。