丹念な聞き込みにより、捜査本部は犯人らが吉林省や黒竜江省などの東北地方出身の中国人らしいという情報を掴む。
「犯人らはおそらく東北地方出身。だが、新宿界隈の東北人たちは、皆、口を閉ざしていた」（警察関係者A）
結束の固い朝鮮族が多く、情報を漏らせば裏切り者として自分の身が危うくなる可能性があるからだ。
事件を起こした中国人は犯行直後すぐに出国し、捜査が難航
主犯は残留孤児2世の東北地方出身者。この確実な情報を捜査員がようやく同じ東北地方出身者から聞き出した時、犯人はすでに国外逃亡した後だった。
「やつらは店長を殺した翌日、中国に帰っていた」（同前）
この頃はまだ、事件を起こした中国人は、犯行直後すぐに出国してしまい、捜査が難航するという問題が事件解決の前に立ちはだかっていた。
しかし、日本に中国人が数多く渡航し居住するようになり、それに比例して犯罪が増加すると、中国の捜査機関や司法当局はそれに対応するべく、代理処罰的な形で犯罪者対応をするようになった。
現在も国外逃亡中で指名手配中
この事件でも中国の公安当局が、国際手配されていた中国人被疑者のうち3人の身柄を拘束。2006年1月、中国の裁判所は日本から提供された事件捜査情報をもとに、主犯格の男に死刑判決を言い渡している。
「結局、犯人は捕まったが、殺人の本当の動機はわからなかった。店長の顔は知っていて、ある時、飲みにいったら冷たくされたからと後の供述で言っていたようだが……」と捜査関係者Aが首をひねる。
残る犯人のうち1人は2017年に日本国内で逮捕されたが、もう1人の郭明宇（グオミンユウ）は現在も国外逃亡中で指名手配されている。警視庁のHPには、歌舞伎町「クラブヴィーナス」内強盗殺人事件の指名手配被疑者として顔写真が載っている。
