This reverts commit bc2a2670 (almost).
It would be best to avoid retrying with the same NS and keep trying with
others (if any), but that would require larger changes if it should work
well, so let's err on the side of sending more queries.