Relativization with Respect to Non-Recursive Oracles
I can't resist putting in a plug for some recent results, indicating that it can be interesting to consider computation relative to the (non-computable) set of Kolmogorov-random strings.

Let $R$ be the set of Kolmogorov-random strings; that is, the set of strings $x$ such that $K(x)$ is greater than or equal to $|x|$.  (Actually, each "optimal" prefix Turing machine $U$ gives a different version $R_U$ of this set; usually it doesn't make much difference which $U$ we use to define $K$; it affects $K(x)$ only by $O(1)$.)

Buhrman et al. showed (at CCC 2010) that $BPP$ is poly-time truth-table reducible to $R$, and earlier work showed that $PSPACE$ is in $P^R$, and NEXP is in $NP^R$.

These might seem like fairly worthless results, since they give a non-computable upper bound on complexity classes!  However a recent paper (see http://www.eccc.uni-trier.de/report/2010/138/ ) shows $PSPACE$ is an upper bound on the class of decidable sets that are poly-time truth-table reducible to $R_U$ for every $U$.  That is, $PSPACE$ is sandwiched between the class of decidable problems that are Turing and truth-table reducible to $R$.  

The same paper also shows that Exponential Space is an upper bound on the class of decidable problems that are in $NP^{R_U}$ for every $U$.  I would guess that it might be possible to characterize $NEXP$ in this way.