Algorithms for spatially indexing points are tractable - see k-d trees etc. R-trees seem pretty lame to be honest, like an ad-hoc data structure to partly meet a number of requirements.
Of course, some kinds of indexing and searching are inherently harder than others. But I don't see why one couldn't program any needed spatial algorithm directly from just an index of all points in the system.
For example, suppose you have an index of triangles. If want to find all triangle intersecting triangle (x,y,z), you could itterative expand a near-neighbor search from each point. Every point you find close than the given triangle-point's further point is a potential neighbor and could checked reasonably quickly. This gives the set S of intersecting triangles to a given triangle in log^n(size(S)), making the process relatively scalable.
K-d tree seem more sensible: http://en.wikipedia.org/wiki/K-d_tree
And there's more: "Storing objects in a space-partitioning data structure (kd-tree or BSP for example) makes it easy and fast to perform certain kinds of geometry queries – for example in determining whether a ray intersects an object, space partitioning can reduce the number of intersection test to just a few per primary ray, yielding a logarithmic time complexity with respect to the number of polygons."
Lends credence to my argument that a polygon-polygon intersection should be obtainable in log^n or maybe even log time.
Space partitioning in general does cool stuff: http://en.wikipedia.org/wiki/Space_partitioning