Way back in the early 70s, I was singing on the street full-time ~ really full-time, 40 hours a week or more actually performing out in public, plus more time playing for myself (practicing) and/or jamming with others at parties or whatever.

I had a number of pretty long songs (mostly, if not exclusively, Dylan songs) in my regular repertoire, largely to help myself fill the long hours. The hardest part has always been remembering the order of the verses ~ my experience was much like that of the original poster; once I have the first line of a verse, I can usually remember the rest.

If I sang verses out of order back then, out on the street, it hardly mattered since my "audience" consisted mostly of individuals who were only present to hear a single verse (at most) while moving past. With time, I'd eventually get the verses in the correct order more and more often, until I had entire songs down pat.

I've started back performing a little bit (one one-hour appearance a month), and nowadays really can't remember lyrics without cheat-sheets, even for not-so-long songs. In my defense, let me note that I rarely need to resort to the lyric sheets except to get the first line of a verse.

So I guess the upshot of my experience is that repetition is indeed the key.