You have the right answer in your choices.
Being a DM isn't about writing a script and continually nullifying player choices to keep them "on script". If you want to write a story without much outside input, then write fiction. Nothing wrong with that.
A DM is only one participant of the story when role-playing. Sure, typically the DM will set up the initial scenario and make certain decisions that will constrain choice. But you have to accept that once you turn the PC's loose on "your" world, they are likely to take your carefully crafted story, and fold/spindle/mutilate it (or all three!).
You can of course plan an overarching story for the campaign. It can a great idea to do so, it provides direction and focuses the campaign. But if the players make the story no longer possible and you can't come up with a satisfying way to "fix" it, then it's time to adjust.
If the party goes off of the rails, it is likely due to one of three things
- They notice the rails and want off! Whether by boredom or active malice they've decided to go left instead of right. Either way, you're getting feedback that your story is not as entertaining to them as you might have thought. Time to make changes!
- Player discovery - The players have discovered something cool about your campaign or their characters that you might not have thought about and want to explore it! This is awesome, it will mean that your story should go on the back burner for a bit. When the players show an active interest in the setting, nurture that, don't shut them down. Let it play out, it usually won't be a long detour and the players will rejoin the main plot-line with renewed vigor.
- Player Agency - One or more players has their own story that they want to explore. Quite often a player will build a backstory for their character that has some hooks in it. If you don't grab the hooks and work with them (I think we're all guilty of this at some point!) the player may still want to explore their half-dragon ancestry, or why they got kicked out of Star Fleet Academy. Let them run with it, rein them back in if it becomes excessive. In the same way that your story cannot dominate the table you can't allow one player to continually dictate what happens next. However there should always be room for each player to shine for a session now and again.
The last two are sides of the same coin. Both involve letting players "run the show" to a certain extent. One problem that I've seen multiple times is for the GM to plan one scenario after another after another, never giving the players a chance to catch their breath. Instead of plotting things so extensively, ease up occasionally. Let the players know that after the current big boss is killed that there are no immediate plans for the campaign and ask, "What will you want to do?" This can serve as a release valve and free up any building tensions.
Plot Issues
1. Play out the sidequests anyway in the back burner
In a way this feels like a Shadowrun situation, and quite frankly if the players are chasing their own (maybe literal) ghosts, the factions are going to hire someone available to do it. Let the party handle their own stuff and a rival party gets the job. You can resolve the quest any way you feel appropriate for where the plot will develop, but now the players need to fight for their reputations. The next player plot hook could be buried in the rival groups.
2. Why not mix it up?
If the party is supposed to be a group of characters with high impact on their world, there is a way to make the character plots intercede with the core plots, even if they happen just a little off kilter from what you need to accomplish like the job is straightforward but Bob's old nemesis just can't see it go well, or George's scorned love demands a favor in exchange for forgiveness, or Nell's long lost sister might be in the mark faction's castle/town/whatever. While they may seem very divergent, the plot device has a setting for looping things together in the strangest of ways such that they all become related and keep the party together.
3. PC the NPC / NPC the PC
Do you have a specific way you want the quests to go? Follow one of the players on their sidequest (and anyone else with reason to be involved) and pre-gen NPCs for the rest of the characters to play - including a core enough personality to keep them involved. Meanwhile, the party does their quest. It might not be the smoothest accomplishment but it would then be up to you as the DM for embellishments but do reward the core party with the quest items for the players performing well in the side arc. This also gives you play room for fuzzy memory parts that you need to ad hoc or retcon.
4. Save this campaign for later
If the players are giving you enough plot to run a full game, it may mean that you should save this campaign for when you have a more attentive party - especially one where you can tell the players what they're in for to make characters in reaction to it. This is my least favorite idea but if they have these in depth characters that run parallel to the world you're running, it may be worth considering.
Motivation Issues
I'm hoping these are not the CN players who just enjoy what I call the Video Game Experience. To me, the Video Game Experience is that to the player, anything in the environment they can interact with needs to be important, monsters are just experience, and the plot itself doesn't necessarily need to matter if they get the levels and the loot. In this case they are almost turning themselves into NPCs if their actions really have nothing to do with the party.
It may be worthwhile to sit down with them to explain that these characters need a few tweaks to make the game harmonic. While a character can be selfish, the fact is that it's hard to run a full party with the truly self indulgent within it. Tell them that they can keep their characters, perhaps even as they are but the player becomes responsible at least up front with why the character is with the group. After encountering a situations where the characters don't mesh or the lone wolf amidst the team, DMs in my area have started telling people that even if they make characters on their own, it's up to them to make party cohesion work. Sometimes it doesn't matter and the DM holds the leash for some major plot hook, but the fact is that in the seemingly sandbox world you have, the party dynamic is player driven.
Best Answer
Don’t prep plots, prep situations.
I will only be parroting that excellent post by The Alexandrian.
In short, you should not prepare a sequence of events that your players should follow, but you should prepare the environment, the actors, what they are planning to do and how, and allow the players to react to the NPC actions and world events, and in turn allow your NPCs and your world to react to the players.
Look at the article, it raises a specific comparison of how the two types of preparation compare, argues that situation-based prep is not significantly more work than plot-based prep, and links to other GM guidance items to help in designing robust scenarios.