I was asked to comment on "the difference between not having time and non-unitarity of a theory".
Well, the difference is significant. Unitarity of all evolution operators is a general requirement of any theory that satisfies the basic laws of quantum mechanics as well as the basic logical rules of thinking. Unitarity means that the state in the past whose squared norm (length) equals one will evolve into a state whose squared norm still equals one. The conservation of this squared norm is what mathematically defines a unitary matrix (or unitary operator) - it is a complex generalization of an orthogonal transformation. Physically, this conservation is necessary for the sum of the probabilities of all alternatives to be equal to 100 percent.
Unitarity holds for all theories that are described by a hermitean Hamiltonian, even if they are time-dependent; it follows, roughly speaking, from the fact that the expoential of an antihermitean operator is automatically unitary. Unitarity also holds for curved backgrounds with no preferred temporal or special coordinates. Indeed, the requirement that the total probabity of all options equals 100 percent is more general than some assumption about the shape of the spacetime.
Let me emphasize that unitarity has absolutely nothing to do with time-translation invariance because the opposite statement is a very popular misunderstanding widespread between the layman physics fans. Time-translation invariance is, according to Noether's theorem, equivalent to the existence of a conserved quantity: in this case it is a conserved (time-independent) Hamiltonian. But even time-dependent theories must preserve unitarity which is something completely different from the existence of a time-independent Hamiltonian. Unitarity must be preserved in all acceptable coordinate frames, for all evolution operators relating any two spacelike slices. All observers agree that unitarity holds - it is nothing more than the claim that the probabilities of all outcomes sum to 100 percent, and that the probabilities are always numbers between 0 and 100 percent. (Possible exceptions need to involve a crazy causal structure of spacetime with horizons or wormholes.)
Once again: for theories with the Hamiltonian, time-translation symmetry means that the Hamiltonian is time-independent, while unitarity means that it is hermitean - these two are very different conditions.
Unitarity also holds in all physically acceptable theories that do not have a Hamiltonian. The only physical and covariant observable calculable in a theory of quantum gravity on a flat background is the S-matrix; by this sentence we mainly mean that the correlators of local fields (Green's functions) simply cannot be gauge-invariant (invariant under all diffeomorphisms) because the position of an operator is modified by a coordinate transformation. It is completely essential for the S-matrix to be unitary, and the S-matrix resulting from any accepted background of string/M-theory (or any other theory treated seriously by physics) is, of course, unitary.
Unitarity is a requirement that does not care about the existence of a priviliged time coordinate. Indeed, a quantum theory including general relativity must still preserve unitarity. But I would go further. Even if we imagine a theory in which space and time are completely emergent, unitarity - or something equally constraining and more or less equivalent - will have to hold. We can generalize the ways how we describe the state of the system in the past and in the future and how we generalize the question "when and where" it is - ways that do not have to require a pre-existing space and time; we can find new complicated mathematical frameworks to calculate the evolution operator (and dynamics in general). But we will never be able to avoid the requirement that the probabilities are preserved.
Note that this requirement cannot be fooled just by dividing all probabilities by the "wrong" total probability, so that the "normalized" probabilities sum to one. Such a rescaling of probabilities would contradict locality and causality. If one investigates the EPR effect carefully, it can be seen that the information cannot be sent faster than light. If the probabilities were divided by a non-local function (the total probability different from 100 percent), the superluminal signals would become physical. That would contradict causality (and special relativity).
A theory that does not preserve the total probability is either a bookkeeping device for an incomplete theory in which the "missing" probability describes the sum of all possible outcomes that we do not want to distinguish (for example, the evolution operator for a kaon does not have to be unitary as long as we interpret the missing probability as the probability that the kaon has decayed into one of many possible final states that are not interesting for us anymore), or it is a proof that a "theory" meant to be complete is actually dead.
Unitarity is usually meant to represent the fact that the total probability is conserved, but it is also assumed that it includes the condition that the probabilities of all possible states in a theory are non-negative (the Hilbert space is positive definite). This condition follows from our experience that the probabilities can never be negative.
While the "conservation of probabilities" is a relatively easy condition that only eliminates the "really sick theories," some theories may survive this test, but they still allow negative probabilities. For example, a quantum field theory with a tensor field leads to many excitations of this field which transform as many components of the tensor. All the components whose total number of temporal indices is odd lead to excitations with negative probabilities. That's not acceptable, and it means that for every such a tensor field there must be a corresponding gauge symmetry that eliminates all these wrong components: it "decouples" them from the rest of the physics and we can forget about them.
The electromagnetic potential A_mu is the simplest example. The electromagnetic U(1) gauge invariance saves us, however. The 3+1 original polarizations of the electromagnetic field are reduced to 2 physical polarizations (e.g. left-handed and right-handed, or - equivalently - x-polarized and y-polarized). One of those 1+1 polarizations is "pure gauge" - a quantum of the transformation itself - while the other is killed by the Gauss constraint. Let me emphasize again: the condition that these unphysical states are decoupled are required in all backgrounds, even very curved ones.
In quantum field theory, the only working gauge invariance for massless spin 1 fields is Yang-Mills invariance which can be non-Abelian. The only working gauge invariance for massive spin 1 fields is a Yang-Mills invariance broken by the Higgs mechanism. The only gauge invariance for light spin 3/2 fields is local supersymmetry, and finally the only allowed gauge invariance for massless spin 2 fields is Einstein's diffeomorphism symmetry. Higher spin fields have gauge symmetries that are so constraining that they don't allow any interactions. This is what allows us to focus on fields with spins 0, 1/2, 1, 3/2, 2 at low energies.
All these statements above follow from the arguments in field theory (or quantum field theory), but they are also independently confirmed by the models of string theory which is not based on a theory directly defined in spacetime. String theory allows various loopholes - for example new acceptable gauge invariances for higher spin massive fields, but only assuming that they come in infinite families and describe all possible fluctuations of a string.
The idea that we will be working without unitarity - and without any equally powerful replacement for it - does not seem to me as a piece of physics, but rather a piece of ignorance. The concepts in physics may become obsolete, but the truly essential concepts in physics can never be eliminated without a replacement.