Since Strahd is technically the only one with the power to let people through the mists, the players can deal with him rather than killing him. The Vistani can spill the beans on that. Maybe the players approach Strahd and ask "What'll it take for you to let us out..." Or maybe Strahd appears to the players and says "In return for X, I'll let you go." There's precedent for that in modules from previous editions.
Of course, since you want to enforce the idea of choice, the deals Strahd offers should be morally gray ones. For example, "The baron of Vallaki is weak and I have someone stronger in mind to manage the town. If you can put Lady Wachter in power, I will let you go." Turns out both the Baron and Lady W are terrible people, and once the players get involved in the politics of the town they can decide which way to go with that.
You can also play Strahd as sympathetic, while he messes with the PCs. He can meet them early on in Barovia Village, and tell them about this family of ruffians who are inciting discontent and generally trying to cause trouble everywhere they go. These rabble-rouses own the winery at the other end of the valley, and use their wine as a way to gain favors from people and whisper lies in their ears. Strahd would be happy to let you leave Barovia if you could help him bring peace to the valley by eliminating these malcontents. Of course, he's talking about the Martikovs, and what starts out as a manhunt may end very differently once they actually meet them... It becomes a matter of his word against theirs, how will they sort out the truth?
There's nothing that says the characters can't "deal" with Strahd to gain their freedom, and I'm sure there's all manner of nasty favors they can do for him, witting or not. Although our group has gone the classic route of "find the artifacts and kill the vampire", if I were to do it again I'd have Strahd meet the characters as they enter his realm, introduce himself as it's lord, and try to gain their trust and alliance. Only once they started really investigating things would they find he twisted the facts to meet his own ends, and what sounded like totally reasonable requests for help are really serving darker ends. I think that would be quite an intriguing way to play it out.