I can only speak for Germany, but as far as that is concerned, the explanation is relatively simple. It can be put into three words: Second World War.

The most obvious result of WWII in Germany when it comes to censorship is of course the legal ban on symbols of unconstitutional organizations, like the swastika. This has led to a number of games being banned for their references to National Socialism, most famously Wolfenstein 3D.

A less obvious result is the impact that WWII had on German society. Ever since the fall of the Third Reich German society has been decidedly pacifistic. With the memories of the catastrophic past still vivid, nonviolence and the opposition to hatred have become a cornerstone of German education. This, combined with the historically strong German tendency towards over-regulation and bureaucracy, has created a way too powerful institution called BPjM which monitors all types of media, including video games.

The fact that this is indeed a result of Germany's troubled past becomes especially apparent if you look at what is generally not censored: Sexual content and indecent language. When it comes to those German regulations are often more lenient than those in the U.S. There is no bleeping on TV for example and you can regularly see content on public television that would only be shown edited or on premium channels in the U.S. Only when it comes to depictions of violence are German laws significantly stricter, even compared to other European nations.

As to why censoring of violence is disproportionately high with video games as compared to, say, movies, I can only guess. I assume that the relative newness of the medium and the general public's unfamiliarity with it help to stoke fears and make censorship seem more desirable. The sensationalist reporting in the German press that has linked several killing sprees to games like Counter Strike certainly didn't help either.