Can we perform an n-d range search over an arbitrary box without resorting to simplex methods?
No.

Rotated-box queries and simplex queries are both generalizations of slab queries, where a slab is the volume between two parallel hyperplanes.  Most lower bound proofs for simplex range searching actually assume that all query simplices are slabs of constant thickness.  In particular, Chazelle [2] proved the following theorem.


  Let $P$ be a random set of $n$ points, generated independently and uniformly in the unit hypercube $[0,1]^d$.  With probability at least $1/2$, any data structure of size $s$ that answers queries in $P$ for slabs of width $1/24$ in time $t$ in the semigroup arithmetic model must satisfy the inequality $st^d = \Omega((n/\log n)^d)$, or $st^2 = \Omega(n^2)$ when $d=2$.


The constants $1/2$ and $1/24$ are not particularly important here; different choices merely change the constant hidden in the $\Omega(\,)$ notation.  Thus, if you are allowed only linear space, your query time must be $\Omega(n^{1-1/d} / \operatorname{polylog} n)$; on the other hand, if you require polylogarithmic query time, you must use $\Omega(n^d / \operatorname{polylog} n)$ space.

More recently, Arya, Mount, and Xia [2] proved nearly identical lower bounds (under some reasonable assumptions about the underlying semigroup) for the even simpler case of halfspace queries, where a halfspace consists of all points on one side of a single halfplane.

tl;dr: Don't rotate your boxes.




Sunil Arya, David M. Mount, and Jian Xia.  Tight lower bounds for halfspace range searching.  Discrete &amp; Computational Geometry 47:711–730, 2012.
Bernard Chazelle.  Lower bounds on the complexity of polytope range searching.  Journal of the AMS 2(40):637–666, 1989.