Replayability really depends on what kind of player you're facing, and what kind of mission it is you're making. E.g. a mission like Steal the Car, which was basically just a couple of minute-long romp through town, possibly not exchanging a single shot with anyone, can be replayed a hundred times just BECAUSE of this simplicity - you can just load it up and start at a new, random location, with new, random enemies all round, that you can then proceed to either avoid or hunt down. It was perfect for e.g. testing total conversion mods, killing five minutes just for fun, etc.
Problem with these kinds of "simple" missions is that generally a neophyte editor can create just as good, if not better, missions in five minutes in the editor. Smack down some OPFOR, give them some "probability of presence" and a random spawning area + a Guard or S&D waypoint, then smack down your squad, and go hunting. Want to move location? Select and move the whole shebang someplace else. That's why missions like Steal the Car, although replayable, don't really cut it for me when it comes to actual replayability.
What makes your regular-sized missions replayable is often what makes regular games replayable. The option to take several different paths, with different outcomes, facing different opposition and getting different support every time, changing the game dynamics. In ArmA/OFP, this is ridiculously simple to do thanks to the AI, the open world, and the easy-to-use editor. On the other hand, this kind of randomization might actually take the "playable" out of "replayable" - how is the mission-maker supposed to be able to balance the mission to be fun and engaging, seeing as one time there might be massive opposition and another almost none? This, on the other hand, can be fixed by allowing the player some control - for instance allowing the player to pick difficulty beforehand, or to decide certain parameters (enemy reinforcements, friendly reinforcements, support, time of day etc.).
And then, of course, there are the missions DESIGNED to be replayable and dynamic - but once again it's important here for the designer to make the mission PLAYABLE - replayability is all nice and well, but if it's no fun...I personally find the story elements and specific design (bunker placements, enemy unit placement etc) to be a big part of a mission's playability, and that's something truly dynamic missions need to contend with. For instance a mission made with DAC can be very nice-looking, with generated bases and patrols - but do the patrols make any sense, do the base placements make any sense? Usually the answer is no - and that's the price you have to pay for truly dynamic and randomized systems like DAC.
So really, replayability is an eternal balance between too much and too little. I could rant on about this for some time, but I think I'll give it a rest for the moment