I totally agree that this is something we rarely see in games, and there is a obvious reason as for why we don't. How often is it that 'beauty' is something that a developer actively sets out to make? A typical AAA studio's understanding of it is simply 'nicer foliage shaders' or '4096x4096 grass textures'. And your right, Sword and Sworcery really gets it: "Small pieces of beauty for you to discover through the exploration of the world." is exactly what Superbrothers set out to achieve, and they pull it off. A real sense of place is something that games are so uniquely capable of, and yet it is something developers so rarely achieve to the medium's potential. In AAA land, some parts of Half Life 2 come to mind though as achieving it. Half Life 2 Art Director, Viktor Antonov really knows his stuff, and I'm hoping to see him pull it off in Dishonoured.
Apart from Sword and Sworcery, there are a lot of indie games that set out to create the same type of immersiveness. Nifflas has been making them for almost a decade now, and I'm kind of surprised to not see his name pop up so much here. Knytt is a good place to start, and the only latest work of his that hasn't nailed it is FiNCK, which was the only one not designed with immersion explicitly in mind. Another not mentioned here much would be the Japanese oddity Yume Nikki. It flails around in the dark a lot, but occasionally hits its mark, look for the Docks and the Rooftop. Also very much of note, the bizarrely massive popularity of Yume Nikki with the 'chans has spawned a incredible amount of fan-games, almost a genre of its own, all of which could be considered Notgames. Maybe we should start a topic about this, it's pretty relevant no?
http://yumenikkifg.wikia.com/wiki/Category:Fangames Is a directory of the bigger ones. Note that the larger fangames like Yume 2kki have hundreds of areas, by dozens of contributors. Sadly, none of the fangames even come close to the original, and like I said, the original is far from perfect. But with an entire scene dedicated to making exploration notgames, its only a matter of time. I hope.
And finally: The Void.
http://www.youtube.com/watch?v=h-ccIGK2FtQ. Oh, and how can I forget Outcry, a modern Myst 'clone' that really gets it:
http://www.youtube.com/watch?v=k9TOHWjINq0.