The downside with always-unique cookies would be that you'd necessarily need some lookup data structure on both alloc and free, which is gonna be pretty expensive, both in memory usage (at least 16-byte entries, multiplied by load factor) and performance (essentially guaranteed cache misses on both alloc and free, unless you have generational lookup tables). Or, worse, some tree structure if you don't want some allocations to have to resize the entire hashtable. That's two things from the GC world - generational allocations, and stop-the-world pauses vs even more significant overhead :)

What it solves is double-free, not use-after-free; potential corruption (even if not of the allocator state) is always gonna be a problem with any allocator that ever reuses memory.