Since the beginning of his recording career, Al has made a point of obtaining permission for his song parodies. He isn't legally required to (American copyright law considers it "fair use", since the audience is meant to tell the difference between the original and the parody), but he does so anyway to maintain friendly relationships with other musicians.
In the case of polka medleys, the original songwriters and publishers must unanimously agree to receive a reduced royalty rate based on what percentage of the medley each song takes up; paying the full royalty rate would cost too much, and Al can't make exceptions so as not to give some artists preferential treatment.
Most artists consider it a point of pride to be parodied by Weird Al (Nirvana notably felt that they had "made it" when Al released "Smells Like Nirvana"), but some have refused permission for one reason or another. What follows is a list of some hurdles Al has faced in parodying other musicians.
- Prince was known to consistently turn down Al's requests to parody his songs over the course of his career. Al asked to parody "Let's Go Crazy" (the lyrics would have been about The Beverly Hillbillies; he later re-used this idea for his Dire Straits parody "Money For Nothing/Beverly Hillbillies*"), "When Doves Cry", "Kiss" and "1999" (which would have been about a toll-free number one could call to order anything), but the answer was always "no". Al eventually stopped bothering to ask, and any hope that Prince would eventually relent ended with his death in 2016.
- When Al was slated to be seated in the same row as Prince at the American Music Awards, Al (and others seated in the same row) received a telegram from Prince's management demanding that they not make eye contact with him.
- Al wrote a parody of Paul McCartney & Wings' "Live and Let Die" titled "Chicken Pot Pie", but McCartney refused permission to record it on the grounds that he's a strict vegetarian (ironically, so is Al). Al has never released the song commercially and has only performed it live.
- Al also wrote a parody of Michael Jackson's song "Black or White" titled "Snack All Night"; historically, Jackson had been enthusiastic about Al's parodies of his songs, but refused permission in this case because the regarded the subject matter of the original song as being too important to parody. Like "Chicken Pot Pie", Al has only performed this parody live.
- Though Led Zeppelin guitarist Jimmy Page is a fan of Al's, he refused permission for Al to create a polka medley of Led Zeppelin songs; Led Zeppelin is notorious for rarely granting permission for their songs to be licensed. Page later gave permission for Al to include a snippet of their song "Black Dog" (re-recorded by Al's band) in the middle of "Trapped In The Drive-Thru".
- "The Alternative Polka" from Bad Hair Day originally had Weezer's "Buddy Holly" in the medley (after Smashing Pumpkins' "Bullet With Butterfly Wings"), but songwriter Rivers Cuomo asked that it be removed at the last second, after it had already been recorded; Al was forced to physically edit it out of the master tape before the album was released. Al later posted a video of the excised recording on YouTube.
- Al believed that he had obtained permission from Coolio to record "Amish Paradise", but after the song was released Coolio claimed that he had actually refused permission and disliked his song being parodied (though he didn't pursue legal action). Al regretted that he had offended Coolio and since then has tried to obtain permission directly from the original artists whenever he can.
- Coolio and Al apparently made up at a trade show in 2006, and in 2014 Coolio said in an interview, "I was being cocky and shit and being stupid and I was wrong and I should've embraced that shit and went with it."
- Al obtained permission from James Blunt himself to parody "You're Beautiful" as "You're Pitiful" but Blunt's record company Atlantic Records refused Al permission before it was released. As it had already been recorded and was intended to be the lead single from Straight Outta Lynwood, the release of the album was delayed. Al then released "You're Pitiful" as a free download on the Internet, as he had no problem going against the wishes of a record company as opposed to a musician.
- A similar controversy occurred in 2011 when Al asked for permission from Lady Gaga's management to parody "Born This Way" as "Perform This Way"; Gaga's management demanded Al finish writing and recording the song before eventually refusing permission anyway. Again, Al released the song for free on the Internet, not wanting to waste the money, time and effort put into writing and recording the parody. It then became known that Lady Gaga herself loved the parody and that her management had refused permission without her knowledge, contrary to what Al had been led to believe. "Perform This Way" was then released as the lead single from Alpocalypse as planned and the royalties were donated to the Human Rights Campaign, an LGBT advocacy group.