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.
You could also xor the memory location into the marker to avoid multiple collisions for applications that allocate a large amount of similar objects.