Until recently, the majority of cover songs uploaded to YouTube were technically illegal, falling outside the boundaries of fair use because of publishing laws. The often-ignored law in question is United States Code Title 17, Section 115, which makes cover recordings legal if the performer notifies the rightsholder. However, with almost 10 million hits for "cover song" it's clear that not many people are either aware of or concerned by the nuances of the law.
YouTube has recently negotiated blanket licenses (which give publishers a share of a $4 million advance pool along with a 50 percent share of any advertising revenue on cover performances) with a number of music publishers, but hasn't provided any way for users to check whether their cover will infringe the law. Worse, YouTube has a three strikes policy, where if you're found to have submitted three infringing tracks, your account will be removed and all of your videos deleted.
In an article for Wired, Andy Baio argues that these restrictive laws are limiting creativity, and punishing artists whose creations don't offer any real threat to the original songwriter's income. He also points out the risk of using tools like Content ID to "fingerprint" tracks, citing one uploader who received eight consecutive takedown notices from companies who believed they owned rights to the public domain movie Night of the Living Dead by George A. Romero. Baio calls for reform, and for those sitting with two strikes and wondering whether their next track is illegal or not, that can't come fast enough.