Mart was kind enough to promote his theory from the comments section in Roadmarks up here in to its own post. He speculates that Leila and Strangulena are the same person.
Here's the body of the comment:
Toba recruits her in the future - as Strangulena - and they both go to the C sixteen tavern.
Still there three days after the black man assassination attempt, and discovered by Red in a burning bed. Red departs.
While there she goes off with "The Victorian Gentleman" (Jack the Ripper - not explicitly stated) and kills him (I think).
This causes an argument with Toba.
Randy and Leaves arrive. She recognises Leaves and leaves (sic) with them - abandoning Toba.
In Two (10) - Chadwick says“The woman with the deadly hands and the custom you found so delightful. She simply vanished. Went off with a new boyfriend and never came back.”
In addition, both Strangulena and Leila are described as having flaming red hair.
My initial impression was that they are two distinct characters, but I'm going to read the book again before I'm willing to say for sure. After all, I was wrong about DeVito's theory that Damnation Alley and This Immortal take place in the same continuity, so I don't want to so quick to dismiss speculation this time around.