why did they think this and what made them stop?

I found three different explanations!

1
The probable origin of the story that the English had tails were the Welsh archers and spearmen who were armed with “great knives” (grand coutilles) which were worn pushed through the belt at the back when not in use. The Welsh being mostly poor at the time seems not to have been able to afoard neither proper sheats for their ‘knives’ nor proper swords in the early parts of the 100-Years war.

2
One of the oddest phenomenon of the medieval period was the belief that the enemy had tails. The Scots said it of the English, the English said it of the French, and it seemed to be a common insult to hurl at one’s opponents.In his chronicle, ‘The Scotichronicon’ (c. 1440), Walter Bower relates the story of how some of the English acquired their tails. Apparently, in 597, when St Augustine came to preach the word of God to the West Saxons in Dorset, he came to the village of Muglington where the people distorted and contradicted what he said, or simply wouldn’t listen to him. They even had the audacity to hang fish tails from his clothing.The story goes that God decided to punish these Saxons, along with their descendants and the rest of their country, for this insult to one of his anointed messengers. As Bower relates: ‘For God smote them in their hinder parts, giving them everlasting shame so that in the private parts both of themselves and their descendants all a like were born with a tail.’ Whether this story was widely known by the Scots, or whether having a tail was simply one of the fashionable insults of the day is not known. We can only assume from the level of violence between the two nations at the time that worse slurs were traded.

3
The final and most bizarre stereotype of the English, one that emerged in Henry II’s reighn and lasted until the 17th century was they had tails. This arose from a miracle story, first appearing in Goscelin of Saint-Bertin’s account of St Augustine, in which the inhabitants of a town attached the tails of some rays to the saint’s garments to drive him away. Wace gave a version of this in which the saint prayed for vengeance and God cursed his persecutors with tails. Form there the image spread to the English as a while, and, as Lawman wrote in his translation of Wace, Englishmen in foreign lands ‘had red faces’ as a result and were called base when abroad. As Lawman’s passage suggests, this ridiculous idea soon gained widespread currency. It has been sugested that Nigel Wireker was playing with this steretype when he wrote that the ass Burnellus, who wanted to lenghten his tail, desired to associate with the English in Paris tobecome more like them. A French poet, Pierre Riga, made a punk on the English “causa” (cause or case) and the English “Cauda” (tail). and Becket may have been playing with the idea in a letter to Gilber Foliot.