I remember being horribly disappointed in the whole last half of SEARCH FOR SPOCK, to the point of being really angry. I wrote up a 4 page story right away that basically said, 'if you've going this route, then you really go this route,' that Kirk and co stay renegades and live out their golden years on the BoP. You save a ton of money on all the earth stuff that goes into act one that for me is essentially baggage, and can put it into real production value on new stuff.
Fairly fannish stuff, but I think it went like this:
picks up shortly after SFS, with the Bop being chased away from Vulcan by Feds, who really want this swept under the rug due to an upcoming big Kling/Rom conference taking place close to the edge where kling, rom, and fed space overlap.
BoP abducts Carol Marcus from Regula. Spock is still pretty out of it, but while going through the BoP's files, he gets more and more Spocklike and figures out that there is a big kling plot in the works, of which Kruge was a cog.
Some reflection stuff with the crew over giving up their careers, while Kirk and Carol have it out. Kirk and Spock figure out that the klingon plot involves a staged attack on the rom/kling conference, using something that looks like a federation starship (the fallback plan from klings not actually laying hands on a fed starship) ...
The Feds chase the BoP into Klingon space and hover round there ...
The lesser regular underlings get made up as Klings and have to pass (barfight humor) while trying to get info at a border world while the BoP cloaks its way through a shipyard and sees a fed-starship type vessel leave. The Klings see the BoP and start chasing it toward the border conference. Feds see some of this activity and all the ships that had chased Kirk start following, but from their side of the line.
There was a whole subplot with Saavik that I'm leaving out because I don't remember what it was (spy stuff and her heritage), but ultimately, the BoP shows up at the conference and finds that the fake starship is a dupe for the old Enterprise (how can Feds deny it wasn't the Enterprise if there is no Enterprise left to pull up and show? Video records can be faked.) Anyway, Kirk basically has to kill THIS Enteprise himself, in full sight of the conferencegoers.
The klingon fleet roars in behind the BoP, but the Fed fleet crosses the line now, so you have a standoff ... and then the Romulan ships for the conference decloak in front of the BoP ... and the Romulans start asking the klingons what they are doing with a prototype Romulan Bird of Prey? (this is back when the 'story' was that Kruge had stolen a rom ship, exposition that fell out of SFS.)
More Romulans show up and 'escort' the klingon fleet away while offering safe passage to Kirk & co. The Feds are happy they didn't have to shoot anybody and offer Kirk amnesty, but Kirk blows them off, and the BoP lifts its wing at them to reveal "Private Enterprise" scrolled under the wing as they take off to maybe do some real exploring.
In thinking about it, it IS a lot more fannish than I first recalled, but it would have gotten the whole Kirk/Starfleet thing squared away, so he could get outside the system (which, to be frank, in SFS, made Starfleet and the Feds seem on their way to an X-Files kind of paranoia -- something that seems to pay off in TUC, but doesn't seem very appropriate to TREK.)