You don't store it in main memory, you store it in the directory, aka snoop filter, or whatever you want to call it. The paper actually estimated the overhead and came up with the number 2% for 512 cores, not that high.
The number 2% also is achieved only if you do three-tier organization of processors, and (IIRC) you need to limit the cache broadcasts to within each tier--which puts some sharp constraints on how you lay out cores in a chip. Intel's many-core chips, IIRC, are laid out in a single ring connecting all the cores, which means it's completely the wrong topology implied by the paper.