Windows7 あたりからは、Thumbs.db の作成場所が %LocalAppData%\Microsoft\Windows\Explorerにthumbcache_*.db に変更されています。 それ以前のOSや、ネットワーク上のディレクトリの場合は、そのディレクトリ下に作成されるようです。 旧システムやネットワークからローカルに持ってきたディレクトリにある、大量の Thumbs.db を一括削除するには、コマンドプロンプトを使うと効率が良いと思います。

del /ah /s Thumbs.db

オプションの /ah は隠しファイルを対象とする指定、/s はサブディレクトリを再帰的に処理する指定になります。