Protoss: Not available in Germany. Probably because Generals is banned here. The reason was back then that the scenario was too realistic. Only game I know that got a USK 16 and still banned. Two weeks later the legal system about "youth protection" was changed and a ban with USK 16 would have been impossible.
jamyskis: Not any more it isn't. That was a controversial case though, and very politicised. I can certainly imagine that the BPjM wasn't keen to have its political neutrality questioned, which is why I suspect there was little resistance to the blacklisting being lifted.
The problem is that the first C&C, Red Alert and Tiberian Sun were censored, and the USK 16 certificate was awarded for the censored versions only. Neither game is blacklisted in its uncensored form, they are simply unrated, and I imagine EA just can't be bothered to get it rerated.
If they were rerated, C&C 1 and Tiberian Sun would no doubt breeze though with USK 16. Red Alert 1 is less clear-cut due to the swastikas.
Funnily enough, I downloaded C&C 2 (Tiberian Sun) with addon (it is freeware) shortly ago, and it still is very nice. So I would have liked to have the full series at one central place instead of having all (except 4) spread out on different places, some early games up to RA2 even on CD.