I seem to remember there was a song called 1234 from Regurgitator that was either nonsense, or impressively incoherent. Never figured out which though.
“The Wait” by the Pretenders.
Pretty much anything by Bob Dylan seems to my ears to be utterly and deliberately unintelligible. Ditto for the (already mentioned) Cocteau Twins, with ‘Pearly Dew Drops Drop’ being one favourite example (and may I add, by way of intentional self-embarassment, that back in the day I actually bought the 12 inch edition of this one song).
A couple of songs not mentioned thus far. ‘Mmm Bop’ by the Hanson Gene Pool Anomalies group: I would happily bet anyone any amount of money that, upon listening to this track under perfect conditions anything up to ten times, they still cannot work out more than 10% of the so-called lyrics. ‘Sidewinder Sleeps Tonite’ by REM. My favourite REM track, as it happens, but with that famously obscure chorus line that was even made the subject of ‘what’s he saying?’ phone-in radio competitions (before the era of easy Google search). Anything by The Fall is going to be unintelligble more or less by definition.
CCR has a lot of unintelligible lyrics. Some samples:
I wish dat I way a fasfraytray
Jus a chooglin on down ta New Orlean
- Born on the Bayou
Luv ta kick ma fee w’down da shallowada
Shoofly, dragonfly, get back ta mama
Pick up fla raw, skip ih craw Green River
- Green River
Whenever I hear Dido, it sounds like she cuts words in half and glues them together to make new words:
An deva ni fi coul di dall begray, bu tchyer pic tcheron my wa
Lit remind sme that it sno tso bad, it sno tso bad
- Thank You
How about “Send Me On My Way” by Rusted Root?
Do songs in other languages count? If so, then my vote is for a French artist called Camille.
Pearl Jam “Hail Hail” or as my brother used to call it, the screaming song.
Most famously “Blinded by the Light”.
I heard that the night before R.E.M. did their MTV “Unplugged” concert, the show’s producer was up all night with Stipe and crew as they struggled to figure out the lyrics to “It’s the End of the World As We Know It (And I Feel Fine)”
I will second Yellow Ledbetter, and add that “State of Love and Trust” would be a close second along with many other Peal Jam songs.
Has anybody seen the commercial where the two guys are downloading songs, then trying to figure out the lyrics to “Rock The Casbah?”
"Is he saying “Stomp the Catbox?”
I took years to figure out what Elton John was singing in “Saturday Night’s Alright for Fighting.”
“Don’t give us your aggravation,
we’ve had it with your Death Star plans…”
Wait, that can’t be right. 
(But that’s what I heard for years. The rest of the song isn’t much more intelligible.)
My vote is for Dead Babies. Something about mommie eating egg rolls in excess.
I thought for years that the sister looked cute in her britches and boots.
Surely, I can win this one hands-down with “Paralyzed” by the Legendary Stardust Cowboy. Yes, there actually are words. No, I can’t make out a one of them. If I didn’t know the title was “paralyzed”, I wouldn’t have guessed the word was even in the song.
Walk away Renee
Exactamundo! However, once you see the actual lyrics in print, you realize that you *were * actually hearing them correctly; they’re just kind of abstract and nonsensical. Still a great song though.
Chest Fever, by The Band. Robbie Robertson doesn’t even know the words.
Any number of songs by Kate Bush are almost completely unintelligible; you have to read the lyrics to see what she’s saying. Then they make sense. But she stretches the bounds of pronunciation so as to make regular words unrecognizable.
Max Torque- is this song online anywhere? I have heard much about its legendary awfulness, but have never heard it.
That would describe nearly any song by Starcastle. Perfectly annuciated nonsense.
Sparkly shining rainbows of the universe
Lemon fountains pave the starry mare
Crimson glowers ending in a carousel
Aging nifty glittering repair – Of time!