O que se pode afirmar com certeza é que Círdan era o Eruhín mais velho na Terra-Média, no fim da Terceira Era.
E é muitíssimo provável que ele houvesse despertado em Cuiviénen. Pense, é textualmente claro que Elu era um não-nascido, ele foi contemporâneo de Círdan, e seria também um dos mais velhos, se não tivesse caído na asneira de insultar os anões.
Os elfos eram tão mortais no despertar quanto eram no fim da Tereira Era, só que seus corpos ainda eram novos demais e por isso, mais susceptíveis à morte. Lembre-se que a natureza dos elfos foi definida por Ilúvatar no Terceiro Tema, e, portanto a morte é algo não-natural para eles desde sempre.
Discordo de você, Erundur. Primeiro, há várias referências n'O SIlmarillion que indicam que, no passado, os corpos dos elfos eram mais resistentes do que na Terceira Era. Eis um trecho que elucida isso:
Imortais eram os elfos, e sua sabedoria crescia de uma Era para outra, sem que nenhuma enfermidade ou petilêncialhes trouxesse a morte. Seus corpos na verdade eram da matéria da terra e podiam ser destruídos; e naquela época eram mais parecidos com os corpos dos homens, pois não haviam sido habitados tanto tempo pelo fogo de seu espírito, que os consome por dentro com o passar das eras. (...)
Isso confirma que os corpos dos Elfos eram mais resistentes em sua juventude, do que o eram na época da Guerra do Anel. E de fato a aparência do próprio Círdan confirma isso: ele é o único elfo descrito por Tolkien que tem barba. Acho que o motivo disso é expressar que de fato o Senhor dos Portos era o elfo mais velho de Arda (ao lado de Ingwë e os outros que despertaram em Cuivénen). O trecho continua:
(...) Depois, quando, em decorrência do triunfo de Morgoth e satisfazendo seu maior desejo, elfos e homens vieram a se desentender, aqueles indivíduos da raça élfica que ainda viviam na Terra-média definharam e empalideceram, enquanto os homens usurparam a luz do Sol. (...)
(O SIlmarillion; Do Sol, da Lua e da ocultação de Valinor)
Esse trecho apenas complementa meus argumentos acima.
Quanto à mortalidade dos elfos, é uma questão mais complicada (e menos definitiva). Os espíritos dos Elfos pertenciam à Terra-média, isso é fato. Mas seus corpos eram "da matéria da terra, e podiam ser destruídos". Isso sugere que a morte não é o estado padrão para os elfos, mas também não é inesperado (ou seja, é natural) no caso de situações extremas, como um assassinato ou a morte de Míriel após o nascimento de seu filho Fëanor. Mas seus espíritos ainda perduram, enquanto os espíritos dos Homens partem dos Cícrulos do Mundo. Essa é a principal diferença, e é espiritual, não meramente material. E de todos os elfos que morreram nas guerras contra Morgoth, os únicos a serem re-encorporados foram Finrod, por sua coragem em salvar Beren e desafiar Sauron, e Glorfindel, pela coragem de enfrentar um Balrog e assim salvar Tuor, Idril, Eärendil e os exilados de Gondolin.
Deve-se então definir o que seria a "morte" de fato: se ela seria apenas o perecimento do corpo, isso é verdadeiro desde que Morgoth desfigurou Arda e pôs um fim na sua Primeira Primavera. Por outro lado, se você considera a "morte" como a partida da alma dos Círculos do Mundo, então sua afirmação é verdadeira, embora contribua pouco, porque os espíritos dos elfos permaneciam na Terra-média (à exceção de Lúthien, que obteve permissão do próprio Eru para partir)