Oh! Indigo Prophecy ,how did I forget that one?? Actually that's probably the most like shenmue I can think of, but it's heavy on the supernatural. You could probably get it for most systems, it had a tiny revival recently. I havn't gotten very far in it but def recommend.
And I'd like to refine my original posting and really recommend Risen 1. All of pirahna bytes work is laboroflove kind of stuff and every game they release they try new things to refine their formula and make them more playable, nothing theyve made is 100% good as I've seen but theyre still in business so that's gotta mean something. Risen 1 has the BEST dungeons I've ever played in any rpg, you have to use your own brain and eyes to get through them- much like Shenmue exploration. And the game offers you a variety of paths to a single end also like Shen. If you live in Germany it's coming to Nintendo Switch!