For example Weird Al's songs are parodies but they aren't protected because he is parodying the Amish NOT Coolio.
The parody protection is very narrowly defined, mainly to stop the target using it to squash opposition. You can't automatically use artist X's tune/style/etc to parody politician Y. And just making your own funny version of something is definitely not
Can you give more information about how parody is defined in the context of fair use here? My understanding is that Weird Al would be completely within his rights to make all of his parodies without permission from the original artists, and that he only seeks there permission out of courtesy and a desire to maintain a good relationship with people. The Wikipedia page backs me up on this, although we could both be wrong.
Basically I can parody your work to make a comment on it. I can't appropriate it to parody someone else.
Weird Al gets permission from the artist - but that's mainly a, don't cause trouble, keep the record company happy.
He would still have to pay for the rights to the music owners when the song is used, although the owner of the music rights may well not be the artist. Which is why some songs are performed live but not on the albums - the payment for singing "happy birthday" at a concert is very different from putting out a cd of it.
ps - I am not a lawyer - although my dog has been trained to piss on their BMWs