[Geowuff]

Ok so now I got the reason for the issue:

Indeed my files had wrong tags, I guess a lot of them are due my use of puddletag. I fixed them now using EasyTAG.
I discovered that XBMC had esp. problems, when:

* Track IDs missed
* Artist varies, but Album artist set and always the same

Thanks for your patient folks!