You might want to consider Indiana Jones and the Fate of Atlantis. While it's a point'n click game, ti has some replayability because past the first part of the game, there a 3 ways to get to the ending. So basically, you can do the game 3 times before you have seen it all, which is quite remarkable.
The 3 ways can be chosen depending on your playstyle :
- One is the team way, you have to make use of your partner ability to solve puzzles
- One si the brain way, there are more and harder puzzles that you have to solve alone
- One is the fist way, with more fights and action-oriented

You just have to know where is the moment in the game where you have to choose your way, so that you can replay the game differently.

And great game, btw.

There are also several puzzles whose solution changes every time. For example, you need to find an object and you know it is in a particular place, but there are different rooms where it could be hidden, each one accessible in a different way, and the exact location is determined at random at the beginning of the game.

You can try the FMV Tex Murphy games (all can be found GOG):
-Under A Killing Moon
-The Pandora Directive
-Overseer
-Tesla Effect
Actually, the game is not "randomized" each time you play. Instead, you can choose to be another "type" of character each time (loyal & committed, neutral, scumbag) through some dialogues which leads you to different endings each time. Again, puzzles won't change, only other characters' reactions against you will be different (if I'm mistaken someone please correct me). Also, I am not sure if the above applies to Overseer at all (i.e. I don't remember if that game even had a "moral path" notion at all).

I'm glad to see people still mentioning Blade Runner. One of the best Westwood games, in my opinion.

It also had a different way of drawing graphics compared to most other games like it.

I actually own Indiana Jones And The Fate Of Atlantis, as well as The Last Crusade, I played both many years ago (in German) and had a lot of fun, it's true that IJFOA almost totally meets what I ask for because a lot of arcade mini-games or mechanics are included, and yes, even the branching is different at some point. I recall that I made it to the inner rings of Atlantis but failed to complete the game for some reason. And a lot of good humor too included. So good that they should have made a movie out of it...

My search goes on, the 2 first titles mentioned in my first post would be ideal. Covert Action is here on GOG, but I own it already and play it in DosBox, and there is NO remake of any sort AFAIK, it's unique in its genre, but more an action game, difficult to tell the genre exactly.

The 2nd one, Murder!, is Abandonware since many years and I play it too on Dosbox, I really wonder why no similar game has ever been made, the mechanics are ideal, nice rooms in 3D to explore, all in real-time, you have 2 hours to solve the crime or Scotland Yard takes over...You need to identify the crime weapon and murder motive, there are about 20 people in the house each time moving all over the place. You must question them, find possible witnesses, take fingerprints, listen to possible lies etc. At the end you need to take the crime weapon and arrest the suspect. If you succeed the newspapers will relate your big exploits, fail and be drained into dirt... There are 5 levels of difficulty; changing the house type, date and difficulty will make it up for more than a million different murders to solve. In my opinion the best possible detective game if made today with top-notch grafics and a less clumbsy interface (which doesn't disturb too much anyway).

I for sure will take a look at Blade Runner and the other titles you kindly mention.
Thank you!

Hm, I think I recall stumbling upon one or two newer indie games like that more recently, and I recall it because that randomization/replayability claim would have been a turn off for me and reduced my interest in something I was initially curious about. If only I could remember what those titles were. Not sure if The Sexy Brutale was among them, but having played a bit of it, I don't *think* it will change on a replay (but I actually don't know).

I do know of a detective/murder mystery module for Neverwinter Nights that's supposed to have different solutions and replayability, possibly different culprits each time, Black Thorn by El Dano. And I know I played a user made adventure like that for Fight the Dragon, but I don't remember the name now either. Not very helpful, I know. I could try to find out, if it's of any interest to you, but I suppose you're looking for actual and longer games, not shorter mods?