Eu costumava ter esse problema, com um CD player em um Toyota Camry cerca de uma década atrás (e sinceramente não consigo me lembrar se era estoque ou alguma marca).
Eu nunca descobri o negócio (em alguns anos eu tinha vendido o carro e instalado um novo no meu próximo carro que originalmente tocava MP3's de CD-R's), mas o resultado é que o seu CD player foi projetado para reproduz CDs pré-fabricados e você está pedindo para fazer algo para o qual não foi projetado, por isso é natural obter resultados mistos.
Mas eu notei que algumas marcas se saíram melhor do que outras e que queimar a uma velocidade menor pareceu ajudar. Você mencionou que seu gravador de área de trabalho parece produzir melhores resultados, veja se você pode fazer uma imagem dos discos do laptop e voltar a gravá-los na sua área de trabalho.
Basicamente, será sempre um toque de voodoo até que você atualize seu arranjo. Eu recomendaria comprar um player com um conector de 1/8 "ou um cabo iPod e migrar sua coleção para um iPod e cortar o voodoo do CD-R.