A call to free could write a gravestone into the freed memory, each free call could check for it and only check the free list if it sees that value. This would make a check of the free list rare, especially if malloc overrides the value again.
How would you know it's a gravestone? What if what you consider a gravestone is a perfectly legit byte sequence for a certain program?
That is the reason you check the freelist in the unlikely case that you see it, the cost would average to near nothing except for the memory accesses to set, check and clear the value.
You could also xor the memory location into the marker to avoid multiple collisions for applications that allocate a large amount of similar objects.
Besides, what's the minimum chunk size? Can't be less than the 64-bit word size can it? The chances of a random 8-byte gravestone appearing in legit memory is practically nil. If free() took only 1ns to run and you called it 2^64 times, that would take >500 years.