I've gotten some of those notices on some 1800's Christmas carols, nearly as soon as I posted them. I'd guess the big publishing companies are scanning new videos with software set loosely to identify their copyrighted material. In the case of the carols, there's no question of their being public domain, but there are probably a lot of arrangements copyrighted, which is why they would flag them. Again, it's only a guess, but it's happening pretty regularly on Youtube these days.
There's a lot of original material including mine on the Tube, but the covers get the most hits, like my cover of Greensleeves. The copyright laws were written to protect against any public performance, so they have the law on their side, but what's right feels like: no profit, no foul...