Paiva era um dos elementos em maior destaque do Vitória naqueles anos.
Com efeito, o madeirense contratado ao Farense na temporada de 1997/98 assumiria as rédeas do meio campo defensivo vitoriano com tanta autoridade, que tornar-se-ia uma peça inamovível primeiro para Jaime Pacheco e depois para Quinito enquanto treinadores do Vitória. Seriam 35 jogos com dois golos apontados, o que fizeram dele um dos jovens valores a merecerem ser olhados com atenção pelos responsáveis federativos.
Por isso, no final da temporada, juntamente com o guarda-redes Pedro Espinho e o capitão Vítor Paneira, houvera estado num estágio no Algarve para o seleccionador Humberto Coelho analisar as capacidades dos atletas que tinha à sua disposição no início da caminhada para o Campeonato Europeu de 2000.
Porém, disso nada mais resultaria, sendo que a convocatória para o particular a disputar nos Açores, frente a Moçambique, fora mais uma acha numa fogueira de desilusão que parecia eternizar-se. Apesar das boas prestações, Paiva dificilmente seria internacional, até pela concorrência que tinha na sua posição.
Porém, como escreveu o jornal Sport de 24 de Agosto de 2018, "... a lesão do dragão Paulinho Santos abriu uma vaga na convocatória." Era a oportunidade por surgia e que seria para o jogador vitoriano a que "foi solicitada a presença imediata em Lisboa." Tal levaria a uma situação caricata já que "Paiva teve de se aperaltar com a indumentária da selecção (fato completo), tendo para o efeito recorrido ao WC do avião para a troca de vestes."
Quanto ao jogo, entraria aos 85 minutos destes, substituindo o marcador dos dois golos lusos, Rui Costa. Portugal venceria por duas bolas a uma e o Vitória ganhava mais um internacional... à pressa e que jamais voltaria a envergar a camisola das Quinas, ainda que sonhasse regressar, apesar de modestamente reconhecer que "a qualidade e quantidade de atletas que formam uma estrutura que já vem dopassado dificultam a minha tarefa!” Mas, mesmo assim, seria inesquecível...