Techniques for showing that problem is in hardness "limbo" Given a new problem in $\mathsf{NP}$ whose true complexity is somewhere between $\mathsf{P}$ and being NP-complete, there are two methods that I know of that might be used to prove that resolving this is difficult:


Show that the problem is GI-complete (GI = Graph Isomorphism)
Show that the problem is in $\mathsf{co-AM}$. By known results, such a result implies that if the problem is NP-complete, then PH collapses to the second level. For example, the famous protocol for Graph Nonisomorphism does exactly this.


Are there any other methods (maybe with different "strengths of belief") that have been used ? For any answer, an example of where it has actually been used is required: obviously there are many ways one might try to show this, but examples make the argument more convincing.
Showing that your problem is in coAM (or SZK) is indeed one of the main ways to adduce evidence for "hardness limbo."  But besides that, there are several others:


Show that your problem is in NP &cap; coNP.  (Example: Factoring.)
Show that your problem is solvable in quasipolynomial time.  (Examples: VC dimension, approximating free games.)
Show that your problem is no harder than inverting one-way functions or solving NP on average.  (Examples: Lots of problems in cryptography.)
Show that your problem reduces to (e.g.) Unique Games or Small-Set Expansion.
Show that your problem is in BQP.  (Example: Factoring, though of course that's also in NP &cap; coNP.)
Rule out large classes of NP-completeness reductions.  (Example: The Circuit Minimization Problem, studied by Kabanets and Cai.)


I'm sure there are others that I'm forgetting.