What about “Unchained Melody”? or “The 59th Street Bridge Song”?
A lot of the ones I thought of have already been mentioned (especially “Rainy Day Women”–took me forever to figure that out and buy the cd), but I think I can come up with a few more …
Blink 182, “First Date”–We used to hear it at the bowling alley a lot, and it was the “Forever and Ever” song, to us.
The Ataris, “San Dimas High School Football Rules”–I just really like that title, but there’s no mention of it in the song, of course.
Guns & Roses, “Estranged”–Also known as “That Really Long Song On Illusion 2 That Sounds Like Three Songs Mashed Together.”
Ani Difranco, “Little Plastic Castles”–The title is in the song, but there’s no real chorus. I always called it by the first (and last) line, so it was the “In A Coffee Shop” song.
I’m sure there’s more that I’ll come up with as the day goes on. 
Talking Heads - Life During Wartime
(“This ain’t no party, this ain’t no disco, this ain’t no fooling around!”)
Suzanne Vega - Tom’s Diner
(“Doot doot doot doot, doot doot doot doot, doot doot doot doot doot doot doot doot”)
Now that’s going to be stuck in my head allllllllllll day. I think you did it on purpose.
Pretty much every single song by Led Zeppelin , except for “Stairway to Heaven.”
“Silent Running” by Mike & the Mechanics
“Run Like Hell” by Pink Floyd
“The Logical Song” by Supertramp
“The Load Out” by Jackson Browne (technically part of a medley called “The Load Out/Stay”, but they can be perceived as different songs on the album Running on Empty)
“The Wedding Song” by Paul Stookey
“Ode to Billie Joe” by Bobbie Gentry
“Tubthumping” by Chumbawumba
Loads more here.
That’s not actually the beginning of the song, although it is the most prominent line. It’s the beginning of part 2 of the “first impression”. Ah, prog-rock, when songs had subheadings.
I wish I had a dollar for every time I’ve had to explain or sing part of “For What It’s Worth” because of all the people I know who have heard the song but don’t know the title. I’ve started referring to it as “that song you hear in every movie or documentary about Vietnam or the antiwar movement in the 60s.” That when they make the connection.
The Sublime song “Date Rape” features those words several times, and even though the song turns up in lots of places (it’s a frequent bumper song on Imus In The Morning for one), people don’t seem to make the connection.
I was reading the back of a cd in a music store, some collection of songs from that era, and my husband says, “I don’t know any of those songs.”
I told him he’d know that one, but when he asked how it went I couldn’t think of it. All I could think of was the Muppets in a forest singing it, and when I mentioned that he could sing it.
That’s scary.
Julie
The Clash “Train In Vain”
I also liked Dwight Yokam’s country version of the song.
(Did you stand by me
No, not at all
Did you stand by me
No way…)
“Back to the Basics of Love” (recorded by Waylon Jennings, words and music by Chips Moman & Boddy Emmons)
Let’s go to Luckenbach, Texas, with Waylon and Willie and the boys.
This successful life we’re living has us feudin’ like the Hatfields and McCoys.
I’ve noticed that over time, this song has evolved from its original title into:
“Back to the Basics of Love (Luckenbach, Texas)”
and then to:
“Luckenbach, Texas (Back to the Basics of Love)”.
Best example is “Black Dog”: “hey hey mama, see the way you move, gonna make you sweat gonna make you groove”
dannannanandowdowdeeedledeedle, etc.
A lot of other Led Zep songs have the titles buried in the 3rd verse, like “What Is and What Should Never Be”.
“Bohemiam Rhapsody” by Queen. Personally, I was always surprised how well the rockin’ public to the mix of opera and rock. Also,
[ul]“Long Cool Woman in a Black Dress” by the Hollies
“Shake It” by Ian Matthews (sounds like Stephen Bishop’s “Save It For A Rainy Day”)
“My Back Pages” by the Byrds (I was so much older then, I’m younger than that now)
“Positively 4th Street” by Bob Dylan (You got a lot of nerve to say you are my friend)
“Shout” by the Isley Brothers (“a little bit softer now, a little bit softer now” - common at weddings and bar mitzvahs)[/ul] These are a few which come to mind. Of course, the all-instrumental songs are even trickier! 
- Jinx
A few more:
-
Suite: Judy Blue Eyes by Crosby, Stills, Nash & Young
I used to always ONLY catch the end of this song with all the doo-doo-doo-doots!
I WAG it is the most recognizable part of the song, however. -
After The Gold Rush by Neil Young & Crazy Horse Band (I assume)
(Well, I dreamed I saw the knights in armor shining in the yellow haze of the sun…) Excellent ballad of which the classic (cliche) rock stations ignore.
Keep on rockin’ in the free world!
- Jinx
“Crique Alley” by the Mamas and the Papas. I believe the song is named for some place in the Bahamas (IIRC) where they escaped to start their career, IIRC?
This song is better recognized for telling the history of the band, and mentioning various popular artists of the time. You might recall the line: …And everyone’s getting fat, but Mama Cass!
…Last one, I promise!
- Jinx
If instrumentals count, then “Green Onions” by Booker T and the MGs. I recognized the song because it’s on every soundtrack about the 60s, and I had heard of a song called “Green Onions” before, but it took a while to make the connection between the two. It’s hard to describe it, but it is kinda bluesy and has an organ in it.
Bush’s “Everything Zen”, from the Sixteen Stone CD: Until I bought the CD I always thought the song was called “I Don’t Think So.”
Oh, you mean the song that goes, “You know you make me want to SHOUT! Kick my heels up and SHOUT! Throw my hands up and SHOUT! Throw my head back and SHOUT!” 
Fine man, crazy man, he can’t see. Sound of the sunset, sound of the sea. Uh-ummmmmmm. Uh-ummmmmmm.
and
I told you I’d come back and here I am!
PS. Bienville is my new favorite poster!
Two well known ones:
The Gary Glitter-performed Rock and Roll, Part II (often referred to as “The Hey Song.” Yes, there was a Rock and Roll, Part I.)
The Lee Greenwood-performed God Bless the USA (often referred to as “Proud to be an American”)