I think of this phrase as meaning two people who never liked each other are at odds again.

The Phrase Finder message board includes this: “A translation in 1620 of ‘Don Quixote offers this passage: ‘There’s no love lost,’ quote Sancho, ‘for she speaks ill of me too when she list.'” It also says “several centuries ago, this phrase carried two opposing meanings.” The old meaning is along the lines of “their affection for each other is undiminished.”

The Free Dictionary says this phrase “originated in the 1500s and until about 1800 could indicate either extreme love or extreme hate. The former was meant in ‘No love between these two was lost, each was to the other kind’ ( Reliques of Ancient English Poetry, 1765). Today, however, the term signifies ill will exclusively.”

It seems odd to offer a citation for the obsolete meaning but not for the current meaning. The Don Quixote translation is the best I found.