Yes, this is the key for improvement. It does not have to provide strict upper_bound, but something that >= strict_upper_bound.
Plus, if this approach will be accepted, we should add ability to request block headers sorted by difficulty, starting with the most expensive one and continue in descending order. This would allow to detect flood with even less traffic, like few percents of Max_Blocks.