The rpgcodex-forums are a veritable treasure trove of the weird and forgotten, so Thanks to all the contributors!
Red Ocean (2007, german), an FPS set underwater. Footage on youtube looks good in terms of the shooting, but the review on yiya.de seems to consider it mediocre. Not on steam, but there are some used copies on amazon.de.
Psychotoxic (2004, german), another FPS which seems to be considered average by most reviewers. There is also one good review on youtube, which is more negative, but which also points out that the game went through a rather lengthy development cycle. Development hell might be more fitting though: Their first publisher didn't give them enough money for the initial design vision and they didn't even get all of it, since they (cdv) went bankrupt at some point in development. Add in some lawsuits, money running out and so forth and it's frankly surprising that this one got released at all.
Exodus from the Earth (2008, russian, FPS): Have barely found anything on it, but it's available on steam.
Operation: Matriarchy (2005, russian, FPS): Seems to be just as broken as Psychotoxic from what I've been able to gather on youtube and elsewhere. But it also seems pretty weird and potentially interesting in terms of setting. Maybe worth a look in that regard. Also available on steam.
The Stalin Subway (2005, russian, FPS) and
The Stalin Subway: Red Veil (2006, some kind of follow-up): Not much to say on them, but what little footage I've seen reminded me of the gameplay of Vietcong 2 (quickload-fest). They are both on steam.
You are empty (2006/2007, by the ukrainian MandelArt Plains, FPS): Nice architecture, great atmosphere (soundtrack). There is barely a story in-game, but the cutscenes are really, really good. Was quite surprised. Feels like Half Life 2 with stalkerish vibes thrown in. Quite short, though I liked it that way. Neither steam nor gog have it, but there are still some copies on amazon.de.
Harvest: Massive Encounter (2008, swedish, tower defense/light RTS): You need to collect ressources and ensure energy flow. There's only four turrets, but you can link up as many lasers as you like and missile turrets can be upgraded to either provide splash damage or very long range seeking missiles. I recommend it if you like death stars. On steam. There's also a demo.
SunAge (2007/2008, austrian, RTS): Haven't played it, but the developer fixed some issues and recently re-released it on steam, so that the weird control-scheme should be gone. Somebody mentioned it on some RTS-thread on the codex a while back.
Locoland (2003, russian, RTS): Locomotives and steampunk robots or something like that. Recently got re-released on steam. Snowbird (Eador, RIP) developer mentioned it in an AMA.
The Entente Gold (2004, russian, RTS): They licensed the Cossacks engine and made a WWI-game which seems to play similarly. On steam.
Aggression: Europe under fire (2007, russian, RTS+TW-style map): Have found much meaningful info on it, but the physics certainly seem impressive. On steam.
Pacific Storm/ Pacific Storm: Allies (2006, russian, RTS+Grand Strategy map): Seems to have been well received in Russia and the reactions I have seen on it are mixed, so it's probably worth a look. On steam.
Rising Kingdoms (2005, bulgarian, RTS): Fantasy-RTS by Haemimont who have made Tzar, some of the Tropicos, Victor Vran and Surviving Mars. But as opposed to the all these games, this one still hasn't appeared on steam or gog. I have tried the demo and did rather like it. However, without putting in more time it's difficult to say how well it distances itself from WC3. Or if it even tries to. The glory-system and the conquest of minor races are some interesting twists on the formula, so I have some hope that things turn out more interesting than in Armies of Exigo.