I'd like to see evidence that this happens enough to matter. Any time you use a Bloom filter you recognize that doing great in most cases is much better than doing OK in every case.
What does a bloom filter have to do with this? Generally when someone uses a probabilistic data structure, they ensure its used in a manner that becomes consistent (e.g., as a caching layer). If by not following the dhcp spec, macs are breaking other peoples' connectivity, there's no recovery save them disabling/reenabling the network for them manually.
First, they don't break the DHCP spec -- everything they do is completely within spec. Second, ARP resolution doesn't require any manual resolution. Third, show me that the OS X ARP system is breaking other peoples' connectivity.
The Bloom filter was an analogy. Optimize for the common case, not the rare case.
