The paper claims that stricter rate limits are a possible solution to this issue, and that with stricter limits in place "crawling entire countries would only be feasible for very powerful attackers". I don't think I agree. Take Signal: the authors managed to crawl all US phone numbers in 25 days, using 100 accounts. Their proposed stricter rate limits force an approx 50x slowdown on an attacker (Table V), which seems to imply that over the same crawl period an attacker would require 5000 accounts. If we assume that virtual SMS numbers are around $5 each, then the attack now costs about $25k, which is about 0.001% the GDP of East Timor.
They also propose a global salt as a mitigation. I'm a little confused there too, because wouldn't the salt need to be present in the endpoint application? If so it would be trivial to extract.
Their proposal of using a key stretching hash algorithm (e.g. Argon2) seems reasonable? At a significant increase in cost on the server side.