I forgot to mention one fact: GEMA has nothing to do with recording copyrights. They only deal with writers copyrights (music, lyrics) and collect the money.
For the recording copyrights in Germany there is GVL. The message when you try to play the video is "this video is not visible in you country, because GEMA did not grant the respective rights"
So it's not Universal. I could imagine though, that Universal has the contact address at Youtube that I am not given here, so I will contact them.
It's amazing, how YouTube can afford to have NO customer service. Well, it's actually Google. I've seen this on Myspace before... bye bye YouTube...