They never lost it, as they never had it. The "lisp" is a relatively recent development in the Peninsular Spain, and even with that in mind, it is not spread throughout the whole country even nowadays. There was a rather notorious shift in pronunciation in Spain across the 17th century that we call "the readjustment of the sybilants".
Nowadays, in Spanish, we have only one sibilant, the s. Back in the 16th century, there were five: s, x, j, z, ç, plus ss.
The classsical Castilian pronunciation of the Ç would be something between the Italian Z and the Serbian DJ (stronger than the former, but weaker than the latter). It evolved over time, becoming perfectly and completely intechangeable with the letter Z, with no distinction. That's why see in the late 16th century words with two different writings, such as dureza/dureça, fuerza/fuerça, cazador/caçador. The pronunciation of the Z was equivalent to the Italian Z, as attested by the Vocabulario de las dos lenguas Toscana y Castellana, by Cristóbal de las Casas (Seville: 1570).
The X and J are somewhat tricky. Depending on the authors, you may find them both letters equated and in others they point out there is a slight difference. The X was equivalent to the English dygraph SH. The J would be a bit softer, like what it is ordinarily transcribed into English as ZH. Cristóbal de Villalón mentions that the pronunciation of the X and J is the same, though he also comments that it should not be. I quote and transcribe:
La X, en el castellano tiene la mesma pronunçiaçion en el vocablo que tiene la j, larga, que el Latino llama consonante: porque poca diferençia haze dezir jarro o xarro, jornada o xornada, porque todo se halla escripto en el castellano. Verdad es que algo más áspera se pronuncia la x que la j consonante. Y por esta causa digo que se deue aconsejar el cuerdo escriptor sus orejas para bien escreuir: porque el sonido de la pronunçiaçion le enseñara con qué letra deua escreuir. Dirá jarro y no xarro. Dirá xara y no jara. Dirá xabón y no jabón. Y ansí en los demás que se le ofreçieren
Translation: The X, in Spanish has the same pronunciation in the word as the j, long, that the Latin calls consonant: because it makes small difference saying jarro or xarro, jornada or xornada, for everything can be found written in Spanish. Truth is that the X is pronounced somewhat coarser than the consonant j. And for this cause I say the sound writer shall accustom his ears in order to write well: because the sound of the pronunciation shall teach which letter to write. He shall say jarro and not xarro. He shall say xabón and not jabón. And so on with the rest of the cases.
The author of the Leuven grammar of 1559, printed by Bartholomaeus Gravius, is of the same opinion, noting this about the J: J: Se prononce en la mesme sorte deuant vner voielle estant consonante, comme en la langue Latine: comme Iulius, Iulio & comme les François dissent Je & Jamais, pareillement les Espaignolz prononcent viejo, ojo, jamas (J is pronounced in the same manner before a vowel than before a consonant, as in Latin: like Iulius, Iulio & like the French say je and jamais, the Spaniards pronounce viejo, ojo, jamas)
The X and the J evolved both into the modern J sound familiar to the Spanish speaking people, which is similar to the Greek X or to the Dutch G. This development came gradually, but linguists have nailed down its origin to Seville in the second half of the 17th century.
And lastly we encounter the C, and the seseo. The C used to be pronounced as the aforementioned Ç when accompanying the vowels I and E, but was a K when accosted by A, U, and O. Cristóbal de las Casas, in his Vocabulario, comments on the pronunciation of the C:
La .c. con la .a. .o. .u. suena como en Toscano: mas con .e. .i. suena como la .z. con qualquier vocal, o como la .t. con la .i. sucediéndole vocal, como Carcel, Vicio, que suenan como calze, vitio. Esta mesma pronunciación tiene la .ç. que llaman cedilla con la .a. .o. .u. (porque con las demás vocales no se pone) como çanca, çopo, açucar, que suenan como en Toscano zanca, zoppo, zucchero.
Translation: The C, with A, O, U sounds like in Tuscan: but with E or I sounds like Z with any vowel, or like TI followed by a vowel, like "carcel", "vicio", that sound like "calze", "vitio". This same pronounciation has the Ç called "cedilla" with A, O, U (for with the other vowels it does not go) like çanca, çopo, açucar, that sound like in Tuscan zanca, zoppo, zucchero.
By the early 17th century, however, the Ç or Z had evolved towards an S, as pointed out by Sebastián de Covarrubias in his Thesoro: En las sílabas Ce Ci suele sonar como S cerca de algunos reynos, que dizen sebolla por cebolla; otros al revés, pronuncian la C por la S, como ceñor por señor, lo que comúnmente llaman cecear. (In the syllables Ce Ci it sounds like S around some kingdoms, where they say sebolla instead of cebolla; others, on the contrary, pronounce the C instead of the S, like ceñor instead of seño, commonly referred to as cecear [lisp])
The characteristic "Spanish lisp", id est pronouncing the Z, and the C before I and E, like the English "th" is a phenomenon that did not exist when the Spanish started settling in America. It only appeared in the late 17th century in Spain, and it was not something generalised, a fact most notorious in certain parts of Andalusia, Murcia, and Extremadura, where they have seseo. One also has to consider the influences of the ways of speaking present in the Spanish-speaking America, where the indigenous languages did not have a "th" sound, hence making it harder for the "Spanish lisp" to develop or to catch on in there.
Sources:
- Casas, Cristóbal de las (1570), Vocabulario de las dos lenguas, Toscana y Castellana. Seville, Francisco Aguilar.
- Covarrubias, Sebastián de (1612), Thesoro de la Lengua Castellana. Madrid, Imprenta Real
- Villalón, Cristóbal de (1558), Gramática de la lengua castellana. Antwerp, Martín Nucio.
- Gramática de la vulgar lengua española (1559). Leuven, Bartholomé Gravio
- Ariza, Manuel (2012), Fonética y fonología históricas del español. Madrid, Arco/Libros