My personal (not very practical) opinion on it is that any derived work that is musically distinct should be considered a separate work. If it isn't the same tune, it isn't the same tune, even if it is similar. If it isn't the same performance, it isn't the same performance.
In fact, the only thing that should be copyrightable by a composer is a specific arrangement of a melody, not the underlying melody itself. (The problem of course is that this is subjective, and not something the law or technology is well-equipped to decide.)
As for record companies, all they should care about is people ripping off their exact CD's and putting them on YouTube for free and not paying them. In my opinion, it's greed to want a cut of a performance/arrangement/cover of a melody that someone else put all the work into.