That scaling argument assumes everyone pays the global network cost per node, which isn't true. Gossip scales because the cost to each participant is O(connections to my node), not O(connections in the whole network), and it's the per-participant cost that gets paid.