Weird Al rerecords the music, but the notes are the same and that is considered fair use. I know that Weird Al ask for permission from artist before releasing any songs, but it's not something he is required to do.
Using the music verbatim would not likely be fair use, and the videomaker owes a license fee.
EDIT: I asked about licensing fees, and Wiki[1] says that Coolio accepted royalty payments for "Amish Paradise." So I still wonder how 2 Live Crew settled their suit, and I need to get back to work.
Ref: http://www.masurlaw.com/3980/songs-and-records-two-types-of-...
In comparison, if you want to do a parody of a music video--a work that is considered to be on top of the music piece, as opposed to included with it, and thereby requiring a special "synchronization license" to make--using the original recording (which obviously implies the original sheet music), you are then going to have to negotiate with the studio, and they may simply not have any internal mechanism by which you can license it at all (even if individuals there think it makes sense).