DNSに詳しい方お願いします。

任意のドメインのネームサーバから正規表現で問い合わせて、対応するドメインをリストでひっぱってくるなどの方法があったりするのでしょうか。

無い。少なくとも DNS の仕様上は。

特定の実装にそんな機能があるかどうかは不明。

それともなにか謎のデータベースを持っているのでしょうか。

詳細は不明だが、持っているのだろうね。

実際に手持ちのドメインで試してみたが、表だって公開していない（DNS の登録はある）サイトについては

表示されなかった。

技術的に完全な方法ではないが、いろいろな手段を駆使して探し当てているのだろうと推測される。

それともなにか謎のデータベースを持っているのでしょうか。

謎のデータベースを作るのは難しくないでしょう。

aguse.jp を使ってチェックすれば、当然の如く、aguse のサーバで「ドメイン名」→「IP アドレス」という変換をするわけですから、その結果を蓄積してけば、同一の IP アドレスを持つ FQDN を調べる事ができるでしょう。

もちろん、ある時、別のホスティングサービスに乗り換えた、ということはあり得るので、表示する前に正引きしてみて、データベース上の IP アドレスと一致しているかどうかを確認し、違っていたらデータベースを更新する。

仕組みとしてはそんなに難しくないですが、aguse がサービスを開始するに当たって、どの程度、こう行ったデータベースを貯めていたかは分かりません。aguse 自信が蓄積したものの他に、例えば aguse が参照している各種サービスから情報を得ている可能性もあります。

DNS の仕組みとして調べる事が出来ない、という点は、b-wind さんと同意見です。

たんに、IPアドレスからそれを利用しているドメインを引いてきてるだけです。

共用サーバーで試せば、サブドメイン以外にも他のドメインもいっぱい出てきてますよ。

http://www.aguse.jp/?m=w&url=http%3A%2F%2Fwww.kaisernetwork.biz&...

調べる対象のドメインのネームサーバーが、誰にでもゾーン転送を許可している場合は

対象ドメインに登録されている情報をまるごと取得できます。

通常は、マスターとなるDNSサーバーがセカンダリーとなるDNSサーバーに対してのみ許可する設定です。

全世界に対してゾーン情報まるごと持っていけるような設定をしているところは少ないと思います。

nslookupのlsコマンドでゾーン情報の転送(取得)を指示することができますが、権限が無いとエラーになります。