The targets' positions isn't the only thing that brings replayability. Hitman didn't need that, instead it offered a variety of ways to get through a mission and it was still amazing to play over and over again. Don't focus too much on those things is what I am saying.
I don't care so much about targets position. After all it is only a small part of the mission. Once you played through it a couple of times you've found quite a few ways to move around the map. Scouting out where the target might be hiding might be fun but not of high importance.
The guards routine on the other hand can really spice things up and constantly force you into new and exciting situations. To enjoy a game I need that feeling of novelty, otherwise I just feel lika a puppet passively reenacting someone elses story.
deeply immersive story
No one seems to remember this. I hope Arkane doesn't throw this part out the window.
A good story and good gameplay doesn't have to conflict but when they do I always prefer better gameplay over story. A quote from Harvey Smith:
"Story is not the purpose of a videogame. So for us, we want something universal to draw the player in, and then the gameplay is the main star."
I agree with him. A game is first and foremost something you play, and while good story will enhance the experience the game mechanics are what will keep me playing. There is a trend in large blockbuster videogames to focus all their attention on story, filled to the brim with cutscenes and scripted events. To me those games just aren't enjoyable no matter how great the story is.
With all the work Arkane Studios have invested in AI and stealth mechanics it'd be a terrible waste not to let randomized enemy spawns multiply the challenges that bring these features to life.

Just how I feel. Great potential that hopefully will keep me coming back for more over and over again.
I found an interesting quote by Colantonio that seems to enforce randomisation but at the same time undersell the concept:
"Everything is a little different every time. We randomise the position of your targets. The patrols might not be exactly the same"
While nice to hear it sound as if the patrol routes will mainly stay the same, with some small variations sprinkled in. I certainly hope for a bit beefier variation than that.