Existiam, sim, outras porções de terra.
Durante muitas Eras, desde a criação de Arda (Terra), sua forma e superficie foram mudadas diversas vezes. Antes da Terceira Era, existia Valinor, a Terra dos Valar e, por conveniencia destes, dos elfos. Também existiu a Ilha de Númenor, entre a Terra-média e Valinor.
Durante a Terceira Era (o período em que se passa a história de SdA), essas terras já não mais existiam. Valinor foi retirada para além dos cículos de mundo e Númenor foi engolida pela mar.
A Terra-média também sofreu várias modificações desde o início. E boa parte do que existiu também se encontra sob as aguas. E além disso, a TM não é apenas aquele pedacinho de mapa que é apresentado nos livros. No exremo leste existem as terras orientais, habitadas (tanto vários homens de la lutaram a favor de Sauron em O Retorno do Rei). E no extremo sul existe Harad, também habitada (e o povo de lá também lutou do lado de Sauron).
Além do extremo leste da TM, do outro lado do mundo existia uma grande ilha (ou mais de uma), mas não me lembro seu nome agora.
Existiam navios sim, e grandes navegações e viagens náuticas que mudaram os rumos da História.
Bom, eu resumi aqui o máximo que pude e deve haver alguns errinhos aí. No entanto, melhor que qualquer explicações que lhe dêem aqui, é ler O Silmarillion. Tudo o que eu resumi aqui está contado lá! Todas as mudanças que Arda sofreu e os motivos dessas mudanças. E a história de cada ilha ou continente presente ali.
Vou ver se acho alguns mapas de posto aqui. Se a galeria estiver funcionando. Parece que não tava.