I think these people are also being disingenuous about their classification of their "business," stating plainly that they are attempting to skirt trademark law by being some kind of art installation. Either it's a parody with permission from Starbucks (which neither party to the agreement is required to inform the public about) or they're going to be in trouble.
A bit more tangential to the topic, there are an awful lot of details missing from that Stanford link about Weird Al's work.
He can write completely different lyrics and publish them all he wants without getting permission or paying royalties. If he chooses to record his own lyrics (which he holds the copyright on) to the same tune as the lyric he parodies, then he becomes responsible for paying royalties on the musical composition only. Once a song has been recorded and published, U.S. law compels licensing to anyone else to also record and publish their version of that song at specified royalty rates to the original lyricist and the original composer (compulsory licensing.)
Weird Al does seek permission. This is simply a gesture of good will on his part. He is in no way required to seek this permission. He writes unique lyrics to which he owns the copyright, records them to the original tune (owing compulsory rates to the original composer), and he's completely legal without ever having to have sought anyone's permission. And "fair use" never enters the equation because copyright law already compels such licensing.