'Black Stone shrine' should appear under 'Known locations...' It doesn't have any pre-requisites, other than discovering it by following the dirt road. Maybe you're being extreamly unlucky. >_<
yeah the RNG wasn't in my favor, although, today I finally got to discover it. So I guess to avoid the off-chance that something like this happens you could increase the probability of finding that place the more you go through the dirt path.
