Do I need to complete a mission after completing 2 challenges to receive the mission unlock? Does replaying a mission, having completed it without 2 challenges before, change anything?
Getting a challenge to register requires you to complete the mission. Thus, getting a challenge reward to unlock requires you to complete the mission.
You can replay a mission and still have the reward unlock.