Obituaries of dead conjectures I am looking for conjectures about algorithms and complexity that were viewed credible by many at some point in time, but later they were either disproved, or at least disbelieved, due to mounting counter-evidence. Here are two examples:


Random oracle hypothesis: relationships between complexity classes that hold for almost all relativized worlds, also hold in the unrelativized case. This was disproved by the result $IP=PSPACE$, and by showing that $IP^X\neq PSPACE^X$ holds for almost all random oracles $X$, see The Random Oracle Hypothesis is False.
Bounded error randomness properly extends the power of polynomial time (i.e., $P\neq BPP$). This was believed for a while, but later, due to sophisticated derandomization results and their connections to circuit complexity,  the opposite conjecture ($P=BPP$) has become prevalent (although still open). 


Which are some other conjectures that failed the test of time?
$\mathsf{NL} \neq \mathsf{coNL}$. Prior to the result that these two were equal, I think it was widely believed that they were distinct, by analogy with the belief that $\mathsf{NP} \neq \mathsf{coNP}$ (i.e. the general principle that "nondeterministism and co-nondeterminism are different"; this turned out to be false under space complexity bounds that were at least logarithmic).