I thought about using a heat gun, i.e. one for removing paint, but the tube of adhesive to attach it to the new logic board is basically more expensive than to just buy another board that already has the heat sink.
This all really puzzles me though. I don't know what to make of it. There's no way that Apple service technicians would have been expected to remove the old heat sink and reuse it.
The only thing I can think of is that new logic boards came with new heat sinks that just needed to be "peeled off" and stuck on.