My idea is to have a gossip relay running on your home network somewhere, which does all the discovery / retrieval / deduplication / verification, and you can connect your mobile client just to this home relay and get a single feed of your social graph.

For that, slow-ish verification doesn't matter that much. My social graph won't sustain 40 messages/sec, even with 1000s of follows.