I haven't talked to Paul. I didn't know that.. but I should, now you mention it!
Actually, within the same node, CPUs can allocate objects they've freed which have come from another CPU (on that node). When freeing an object to our freelist, the test that is performed is whether the object's memory is on the same node as the node this CPU is on. This is similar to what SLAB does, and indeed is good for cache (and object management overhead).
Except in very special cases of slabs (RCU-ish ones), the linked list is part of the object itself (when the object is freed, nobody else by definition is using the memory). _Often_ in the kernel I'd say that when an object is freed it is probably recently been touched by the freeing CPU. It would be an unusual situation eg. to have a refcount to the object residing somewhere other than the object itself.
And yes, we have the struct page structure for every page in the system, which can be found with calculations on the object address. And yes, all the slab allocators use this struct page to manage their slabs of objects :)