彼氏に盗られたお金全額回収したい

弁護士の費用は、何をどこまで依頼するのかによって、金額は変わってきます。一般的には、着手金（最初に弁護士に支払うお金）と報酬金（本件で言えば、回収できた金額に応じて変動する成功報酬）を支払う契約になることが多いですが、その具体的な内容も、弁護士によって変わります。
事案との関係で、何をどうすべきか、その見通し次第で、弁護士側が適切と考える対応なども当然変わりますから、まずは弁護士と相談して、見通しや費用についても個別に説明を受けた上で、依頼するかどうかを検討されることをお勧めします。

彼氏にお金を勝手に使われた、というお話ですが、彼氏であろうと他人ですから、その男性に無断でお金を持ち出され、あるいは使われてしまった事実を立証できるのであれば、民事的に（あるいは理論上は刑事でも）争う余地はあります。
ただ、無断での持ち出し等に関する証拠が消され、有力な情報が残っていないとなると、当然ハードルは上がります。彼氏彼女の親密な間柄だとして、彼氏側が「彼女から支援してもらった、無断ではなく許諾を得ていた」などと言い訳することが通常なので、十分な準備・検討を要します。
またご指摘の通り、正確な個人情報もわからないままに逃げられてしまえば、どうしようもありません。既に彼氏側が証拠を隠滅するような動きをしているとなると、正確な個人情報についても掴ませないようにしている可能性も十分想定されます。
この手の事案では、彼氏が「会社を経営していた」という話も、それ以外の話も、何もかも嘘だったということが、残念ながら珍しくありません。最初からお金目的で異性と親密になろうとする人間も、少なくありません。

いずれにせよ、まずは個別に弁護士に相談されることをお勧めします。

クレジットカードの使用履歴に関しては，調べれば確認ができるかと思われますので，相手がその金額を使用したことが確認できれば証拠となるかと思われます。

ただ，現金の持ち出しに関しては，相手が金額を認めた証拠がないと，証拠が何もない状態で返済を求めることは難しくなってくるでしょう。

弁護士費用に関しては，事務所によっても異なってくるため，ご相談された際に確認されるのが一番良いでしょう。

相手の電話番号がわかっているのであれば，弁護士であれば契約者情報を調査することが可能ですので，そこから住所が特定できる可能性はあるかと思われます。