I'm looking for artsy / experimental video games with an emphasis on atmosphere or story.

I don't think you can beat The Path for pure wierd. For artsy/experimental try Osmos or Everyday Shooter. There is also the Dreamcast/PS2 classic REZ.

Machinarium? Osmos? Lucidity? Samorost?

I've already played The Path, Machinarium, Osmos and Samorost and I loved them !
I don't know the other games, so thanks, I'll check them. (maybe not REZ because it is on PS2)
But, because we are on good old games, are there any games like The Path or Machinarium, but older ?
And is Lucidity available on another platform than steam ?

Zeno Clash.
Rez is must play. It can be emulated though naturally I wont tell you how.
The free [url=http://www.asahi-net.or.jp/~cs8k-cyu/windows/tt_e.html]Torus Trooper[/url] is a vaguely similar substitute...none of the story/atmosphere though.
Also Harvester Games catalogue.
I think Lucidity is Steam only.
Let me look into GOGs for you..
Edit: Oddworld, Myst/Uru, Another World, Psychonauts, Sanitarium, Feeble Files, Syberia, Longest Journey. Hopefully you like adventure games. ;)
Non GOGs but older: I Have No Mouth and I Must Scream.

How is that game in terms of gameplay and replayability?

Haven't played it.

REZ HD has recently been released on the Xbox Live arcade if you have a 360. If you don't it's not hard to find a cheap Dreamcast REZ on eBay and run the Dreamcast Emulator

I wish HD version was on PC so bad...

Indeed. I still have my Dreamcast and REZ but REZ HD looks fab.

Me too, I would get Rez HD right away if it was available on PC.

The Path
Echochrome

I think a lot of people would. Who knows, Sega loves PC now, so maybe...