She knew from very early on
You are correct, of course, that the interactions between Snape and Lily Evans in Harry Potter and the Order of the Phoenix were definitely written keeping in mind the future revelation of the relationship between them.
However, Rowling almost certainly knew from quite early on. In an interview in October 1999, she said the following:
Q: Do you know what Harry's parents look like?
JKR: "Yes. I've even drawn a picture of how they look. Harry has his father and mother's good looks. But he has his mother's eyes and
that's very important in a future book."
It seems clear that she means Harry Potter and the Deathly Hallows.
“Her son lives. He has her eyes, precisely her eyes. You remember the
shape and color of Lily Evans’s eyes, I am sure?”
“DON’T!” bellowed Snape. “Gone. . . dead. . . ”
—Harry Potter and the Deathly Hallows
This was shortly after the publication of Prisoner of Azkaban, so I think she must have had it in mind as early as the third book. This answer indicates that she had the Half-Blood Prince plot worked out in 1997, i.e. while writing Chamber of Secrets. Of course, this does not specifically mention Snape and Lily's relationship, but given the connection between the two plots, it seems likely that she also had the latter in mind.