HDD故障時の復旧について

海外の業者がどうやって、OS等を入れ直したのかわかりませんが、不正なものがいれてある可能性があると思います。
ハードディスクが完全にこわれたなら、通常はハードディスク交換後リカバリーディスクから初期化するのが普通なのでリカバリーディスクがないと無理だと思います。作っていなかったなら、メーカーから買うしかありません。
リカバリーディスクで初期化した上でバックアップからの復元になるとおもいますよ。

富士通製であればトラブル解決ナビのディスクから復元できます。

>>ただ、HDDが変わっているため、説明書に書かれているようにかんたんバックアップ、マイリカバリの画面は出てきません

通常、ＨＤＤを交換した場合、復元のメニューが出ないことが多いですよ。
フリーや市販のバックアップソフトでも、こういう場合は、復元ソフトをＣＤやＤＶＤなどに入れておいて、それを使ってＰＣを起動しバックアップ・復元ソフトを起動させませます。

バックアップを作成されたソフトで、上記のようなことができるか探してみましょう。
もし、そういうことができないなら、バックアップからの復元はあきらめることになるかもしれませんね。