That’s the first song that came to mind when I first saw this topic. =P Also, Billy Corgan said in an interview that he named the song Mayonaise because he “looked in his fridge and saw mayonnaise, and decided to name his new song that” or something. =P
ANYWAY…
Soundgarden - Never Named
Do songs that have titles that aren’t really random count as long as the words in the title aren’t in the song itself? Even if the song’s title really does describe the song?
If so…
The Cranberries - Ode to my Family
Darkane - Psychic pain
Ha, I found one
Question!- System Of A Down
Aw damn you, I was going to post that tonight. 
EDIT: never mind I’m stupid, it actually appears in the song <.<;
Iron Maiden - Revelations
Tool - Stinkfist
Rise Against - Tip the Scales
Unchained Melody (not sure who the original artist is, but it’s been covered by bands like U2)
I don’t know who the original artist is, but the Righteous Brothers’ version seems to be the definitive version.
Anyway…
Veruca Salt - Venus Man Trap
(Do I get bonus points if the band starts with the letter too?)
Whatever - GodSmack
System Of A Down - X
Pearl Jam - Yellow Ledbetter
Zombie Inc. - In Flames
Another round?
Dream Theater - Achilles’ Last Stand
I sure hope that’s a cover of the Led Zeppelin song.
Bloodhound Gang - The Bad Touch
Hilarious song might I add XD
I’ve got a couple in mind for C… but I think I’ll go with…
The Mamas and the Papas - Creeque Alley