this seems like a very reasonable approach. I'll mark it as an answer for posterity, even though I'm no longer working on this problem and don't have access to the data to benchmark the solution. In the end, I ended up using STRtrees but first partitioned based on some coarse window of coordinates (i.e. I don't care about comparing to very far away points, even if they are the closest ex post)

I'm trying it now on a subset, but it appears to be much slower, even ignoring overhead time to create the tree. (Note: This was my experience when I made a single tree containing all the rooftops.)