What you're thinking of as a "simple linear history" is actually not. Notice that when you rebase there are new hashes for each of your commits.
If you're rebasing your branch with master and resolving merge conflicts along the way, you're going to get bit eventually. Even if you're somehow not dealing with merge conflicts, you're losing your ability to look at the git log and figure out when the last time you synced up with master was.
Long running branches are a bad idea. Try not to do that.
Not everything in a long running branch can be merged; selective things will end up cherry-picked (which is a generalization of rebase). Suppose the trunk maintainers like 75% of what was done in the branch. They might go through the commits one by one and take what is relevant.
When you merge a branch, and want to follow a good SCM process, you must treat it as a closed topic; do not commit anything more to that branch. Start a new branch, even for a closely-related continuation of the same work.
The correct way to merge a branch is to rework every single commit onto the new baseline. That is true whether that rework is represented as a merge, or a cherry-pick. Therefore, we can't avoid the issue that every change turns into a new object with a different hash.
What we can do is put tracking information in the commit message to correlate these together. The Gerrit review system uses a Change-Id: line for this. Each commit has random ID which is not a content digest; it stays the same across cherry picks.
If I'm debugging a problem on trunk T, across some commits that came from a branch R, I do not care what those commits looked like in R. Only in a very rare case will I be interested how a change looked like there. I want every commit that came from R to be reworked on T, as if it was originally developed on T. If I find the problem and have a hunch that it was introduced during the merge, then I might out of curiosity find the commit's cousin in the original R branch just to see how it looked like there. Other than that, I'm shipping T, not R, so that's what I'm debugging.
See https://mirrors.edge.kernel.org/pub/software/scm/git/docs/gi... for more info
The concept of "git bisect" is inherently predicated on a simple linear history consisting of commits that were applied on top of each other. We are searching for the bad one which flips the test case from "good" to "bad".
If you throw an ugly graph into it and merges, it's not even comprehensible. Say that instead of git bisect we just go backwards, commit by commit, starting at HEAD. Oops, we encounter a merge commit: which way do we go now to find the breakage? Parent[0], or parent[1]? Or [2] ...? What is the correct traversal order? Do we go down [0] first? At which commit do we backtrack and try going into [1]?
There is absolutely no issue with git bisect over a repository where you have the unmodified upstream commits, and your own local ones rebased on top of them. It nicely finds the bad commit in one or the other.
Now of course the rebase rewrites your code by merging it (in the real sense of the word). If you discovered the bug yesterday (and it's in your own commits), then you rebased this morning, you're now chasing that bug over different commits that have been subject to auto-merge and maybe even manual conflict resolution. Oh well; yesterday was yesterday! Repro the bug with the newly rebased repo and bisect away.
Or, here is an idea: if you're chasing a bug, don't fetch anything and don't rebase! Right? If you've repro-d a bug, you don't want to start changing code, so the last thing you want is to bring in reams of changes from other developers. I've never rebased while chasing a bug with git bisect; I stopped what I was doing until I found it, in the nice linear history as it existed at that point.
If external forces cause you to drop what you're doing and rebase while you have some bug, what you can always do is "git tag bug-hunt" to set a bookmark where you were. Do what you have to do, and then when you pop your stack, return to that tag and debug from there. You can find the original bad commit. If it's in your uncommitted work, you can cross-ref it to the latest rebase. (There is a chance it might not exist any more; e.g. upstream changes made some of your local code obsolete, so you threw them away in the rebase, and the problem was in those discarded changes.)