Problems Between P and NPC
Here's a collection of some of the responses of problems between P and NPC:

Factoring
Isomorphism problems: Graph Isomorphism [not NPC unless $\sum_2^p=\prod_2^p$] (via @Jeff Kinne), Graph Automorphism, Group Isomorphism, Automorphism, Ring Isomorphism and Automorphism (via @Joshua Grochow)
Computing the rotation distance between two binary trees or the flip distance between two triangulations of the same convex polygon (via @David Eppstein)
The Turnpike Problem of reconstructing points on line from distances (via @Suresh Venkat)
Problems arising from the Unique Games Conjecture (via @Moritz)
Discrete Log Problem and others related to cryptographic assumptions (via @Joe Fitzsimons)
Determining winner in parity games (via @mashca)
Determining who has the highest chance of winning a stochastic game (via @Peter Shor on MO)
Numbers in boxes problems (via @Joshua Grochow)
Agenda control for balanced single-elimination tournaments (via @virgi)
Knot triviality (via @JeffE)
(Assuming NEXP≠EXP) padded versions of NEXP-complete problems (via @Joshua Grochow)
Problems in TFNP (via @Marcos Villagra)
Intersecting Monotone SAT (via @András Salamon)
Minimum Circuit Size Problem (via @Eric Allender)
Deciding whether a given triangulated 3-manifold is a 3-sphere (via @Joe O'Rourke and @Peter Shor)
The Cutting Stock Problem with a constant number of object lengths (via @Suresh Venkat)
Monotone Self-Duality (via @Danu)
Planar Minimum Bisection (via @turkistany)
Pigeonhole Subset Sum (via @user834)
Square Root Sums (via @JeffE)
Deciding Whether a Graph Admits a Graceful Labeling (via @Oleksandr Bondarenko)
Gap version of the closest vector in lattice problem GapCVP$(\sqrt{n})$ (via @MCH)
The linear divisibility problem [known to be $\gamma$-complete but not NPC] (via @Oleksandr Bondarenko)
Finding the VC dimension (via @Mohammad al Turkistany)
Finding the minimum dominating set in a tournament (via @Mohammad al Turkistany)