Funny, almost every r-tree in the codebase at a former job of mine eventually became a performance problem and got replaced by square fixed-size buckets.

Of course, it helped that most of the queries we did could be phrased like "Find all things within a fixed (and known ahead of time) radius of this point." R-trees are much more versatile, but much slower to query and much much slower to construct/maintain.