Thank you for making me feel special! But I don't think 2000 is really such an extraordinary number?
I'm familiar with the underlying logistics, and jamming everything in a single REQ will currently blow stuff up. In an age of multi megabyte websites and gigabyte photo's, 2000 keys is a really tiny number. The array itself is ~160kb JSON. Even for a phone that's peanuts, let alone for a server. AFAIK most relay implementation bumped their max list size a while ago, but that obviously isn't the only issue here.
I never got gossip to work, as I couldn't get it to pick up my follows as well, even when it was smaller. But should indeed try it again.