I was sure I was misunderstanding the paper, but my quick read matches yours. They seem to be analyzing just this one query. Another error is that just counting

I was sure I was misunderstanding the paper, but my quick read matches yours. They seem to be analyzing just this one query. Another error is that just counting the number of times the curve passes in and out of the query is too simplistic. With z-order, and presumably with Hilbert curves, you can grow the query very slightly to greatly reduce this number. Then you just have to filter out the false positives. I've implemented all this using z-order, in a variety of systems, including a relational database query engine, it works really well.