Hello Scott, I was doing some similar back-of-envelope calcs earlier today and came to a similar conclusion. I do think there's a lot of people splitting quite a way below 1,000,000 nodes/tile, but even still a map's far easier to implement than rtrees and is a big win over what we have now so it's probably not worth worrying too much about where the crossover point is.
A 256x256 map would have 65536 cells about 120km on a side. Looking at the overview map of a max-nodes=1000000 split in qlandkarte, which shows tile boundaries,.I'd guess the worst case would be 10-15 tiles in a cell. That would prune away at least 97.5% of the bounds-checks.
With the planet file, at this nodecount and cell size, an R-tree traversal would likely have more boundschecks than that. I could see an r-tree being a win if tilesizes got a lot smaller, say people started to run max-nodes=50000 splits, or spitted files with insane node densities, such as contour lines.
To reduce the memory requirements, sets of candidate areas would probably need to be pooled and reused across multiple points on the density map. I wouldn't worry too much about memory. Absolute worst case is each cell has all 255 areas, which would be 4 bytes * 255 areas IntList * (256*256 cells) =64mb. Use a ByteList and it's 16mb. Bitvector and it's 2mb. More realistically, I'd expect it to be 1/10th of the worst case.
Scott