占いに使った亀の甲羅が発掘されていないと聞きましたが、それではなぜ対馬などの場所を特定できたのでしょう。

どこかで聞き間違いがあったものと思います。弥生時代の鹿を用いた卜骨は列島各地から発掘されていますが、古墳時代以降に出現する亀甲を用いた卜甲は、対馬・壱岐など玄界灘周辺と、南関東の海岸付近からしか見つかっていないということです。それらの地域は、律令国家が卜部の源泉とした対馬・壱岐・伊豆とほぼ一致するので、考古資料と文献史料がほぼ噛み合った状態となっているのです。