Ooh, Untold Legends: Brotherhood of the Blade has to be up there.
Spiders are attacking! Spiders are dead!
Strange monsters are attacking! Strange monsters are dead!
*Repeat for some ten other species*
We must find some dead people's spirits and kill a giant demon who's been controlling all of this!
So cliche.
UT3 had a pretty pointless story, too.
If Soulcalibur IV counts, then that wins. Various random backstories with no real connection, followed by a story that is pretty much completely unchanged for all of the characters.