Maybe rate-limiting as such is not the right idea, but how about just limiting accounts? I think there is a substantial difference between the 4.6mm collected and even a "sufficiently large contact list." There must be a number at which you can be banned from requesting any more.