タイムマシーンに設定する前にあったハードディスクのデータを復元したい

記憶にないのですが、おそらくフォーマットした可能性があります。

これはどういった意味でしょうか？

ni_kiさんがお書きなのは、元元FATフォーマット（正確にはHFS+以外のフォーマット形式）だったHDDだったので、Time Machineとして使おうとするとMacがHFS+にフォーマットをするから、元元がFATフォーマットだったのかとお聞きなんですが、お書きの内容だと「Time Machineとして使おうとするとMacがHFS+にフォーマットをするから」の事を指して「フォーマットした可能性があります」とお書きのように取れますが…。

市販の復元ソフトでは不可能でしょうか？

これは、元元（復元したいデータが入っていたとき）のHDDのフォーマット形式に依るんで、それが分からないと…。なのでni_kiさんはお聞きしたんだと思いますが…。

追記：

ご参考：

「外付けHDDのデータ（Mac→Win→Mac）」

「タイムマシーンができず間違ってHDを消去」

等。

とりあえず、安全な復旧方法を実装しているDataRescueを試用してみては？

それでダメなら、次の手を考えれば良いだけで、心配し過ぎていると、何も進みませんよ。

http://www.igeekinc.com/datarescue4.html

もし、元々のフォーマットがFAT32だった場合は、DataRescueのPC版を使えば復旧出来る場合もありますし。

http://www.igeekinc.com/datarescue4.html#43

もしかしてその外付けはFAT32 フォーマットでしたでしょうか。それだと業者を頼む必要がある気がします。