I think Path of Exile does this kind of procedural generation of areas very well. Generated maps of a specific area will feel similar with some landmarks and the direction you're traveling in, but this is a good thing, because they can be used as guide posts where to go if you're an experienced player.