ご長女については，養育費の支払義務がなくなる，又は，減額できる可能性があると考えます。

養育費は，親子間の扶養義務に基づき支払われる未成熟な子の生活費です。

仮に，ご長女が，正社員等として就職したのであれば，一応経済的独立が可能と認められ，未成熟とはいえないこととなり，養育費の支払義務はなくなると思われます。
これに対し，フリーターとなると，少し話が異なるように思います。
職種や収入にもよると思いますが，いわゆる就職の場合と比べると若干経済的に不安定な感じを受けます。他方で，学生がアルバイトをしているのとは異なり，フリーターとはいえ，仕事に専念しているわけですから，学生とは扱いが異なるのではないかとも思います。

そこで，ご長女がそれなりに安定した職種につき，長期間そこで勤務することが予想され，それなりの収入を安定して得られるのであれば，もう「未成熟」とはいえない経済的に独立した存在として，養育費を支払う必要はなくなるのではないかと考えます。他方で，そこまでは言えない場合でも，ある程度は成熟したものとして，減額は可能なように思います(もっとも，もともとの月4万円という養育費額が適正な場合に限ります)。

１　奥様の転居費用
　　奥様が自宅を退去した理由にもよるとは思いますが，基本的には，折半ないし双方の収入割合に基づく負担ということになるのではないでしょうか。
２　家具
　　これは，お二人が同居するにあたり購入した家具の「購入代金」ということでしょうか。
　　その家具を何年使用したかにもよると思いますが，すでに「中古」の家具となるので，新品の購入代金を請求されるのは相当ではないでしょう。リサイクルショップなどへの売却代金相当額を支払えば十分ではないでしょうか。
３　養育費
　　双方の合意により，養育費額を決めるのが原則です。
　　合意に至らない場合は，双方の収入に照らし，相当額を算定します。
　　養育費は，離婚後，具体的に請求されてから支払義務が生じるので，離婚前に請求されても支払う必要はありません。「婚姻費用」であれば，支払義務はあります。
　　気になったのですが，あなたの連れ後である娘さんと奥様とは養子縁組をしているのでしょうか。
　　仮に，養子縁組をしており，離婚に際し，離縁しない場合は，奥様はあなたに対し，娘さんについての養育費を支払う義務を負います。

親権の争いとなった場合，同居中の主たる子の監護者が誰だったか，現在の監護状況はどうか，お子さんが10歳以上の場合お子さんの意思はどうか，といった観点から検討されます。

これまで，あなたが主にお子さんの面倒を見てきたというのであれば，別居に際し，あなたがお子さんを連れて行って，母子楽しく生活できるのであれば，親権を取れる可能性は高いのではないかと思います。

夫と別居したい，離婚したいというお気持ちは理解できるのですが，別居した後の生活，主に経済面についてどれくらい具体的に検討しているかが重要ではないかと思います。別居に踏み切るのであれば，その前に，具体的にどのような収入を得て，どの程度の支出が生じるのか，シミュレーションしておくべきだと思います。

あなた自身が元夫の住所を調べて，請求書を出すということもできなくはないでしょうが，現実的には，弁護士に，元夫に対して未払養育費の支払いを請求することを依頼して，現在の元夫の住所を調べてもらって，過去１０年分遡って請求する，というのがよいでしょう。

もっとも，お子さん２人に対し月額１万円の養育費すら支払わない男が，たとえ弁護士から請求があったとしても素直に支払うとは思えません。裁判をしても，回収できるかどうかは不明です。
勤務先を調べられたとしても，元夫が勤務先をやめてしまえば給与差押えも空振りになります。

要は，弁護士に依頼して請求したとしても費用倒れになる可能性があるということです。
それでもどうしても支払わせたいというのであれば，弁護士に依頼することをお勧めします。

養育費は，「未成熟の子」に対する扶養義務が根拠になります。
未成熟，とは，平たく言えば，学生の間と言えるかもしれません。要は，経済的に独立していない，できない状態ということです。
そのため，娘さんが大学を卒業した以上は，未成熟とはいえないため，養育費の支払義務はない，と言えます。

なお，「障害等で就職が困難」等の理由で要扶養状態の子がいる場合は，養育費ではなく，扶養一般の問題になると思います。

弁護士に依頼することが前提となりますが，弁護士であれば，⑴支払義務者（元配偶者）の住民票上の住所，⑵携帯電話番号が変更されていなければ，携帯電話業者に登録がある支払義務者の住所を調べることは可能です。
ただ，いずれの手段もある程度時間がかかるのと，⑴については，住民票上の住所と現住所とが一致していなければ意味がなく，⑵については，携帯電話業者の登録情報に現住所が記載されていなければ意味がないことになります。
その点を踏まえた上で，それでも調べたいというのであれば，弁護士に支払義務者に対する養育費の請求を依頼するのがよいと思います。

元妻が再婚し，再婚相手が息子さんと養子縁組をしたとしても，あなたの息子さんに対する扶養義務がなくなるわけではありません。あなたが実父であることに変わりはなく，引き続き息子さんに対し扶養義務を負うからです。

もっとも，現在，息子さんと一緒に生活している元妻夫婦があなたに先んじて息子さんに対して扶養義務を果たすべきであると考えられますので，養育費の「減額」を求めるのは当然に可能でしょう。「減額」が０円まで減らせるかどうかは，事情によるということになります。
そのため，元妻が養育費の支払い免除又は減額を受け入れないのであれば，養育費減額調停を申し立てるべきということになります。調停の中で，元妻夫婦の収入資料を提出させることになります。

あなたの現在の奥様の収入が考慮されるのか，については，あなたたち夫婦の間にも子がいて，２人で扶養していることから，息子さんに対する適切な養育費額を算定するにあたり，問題となるだろうと考えられます。