... I experimented: workbook A contained a link to
workbook B. I saved them both in the same folder, then moved them to
another folder. When I opened A, its link correctly pointed to B in
its new location.

I did a similar experiment, with a similar result.

Things seem to work best if all the files are in the same directory, and
you copy them together to a different one.

I created the links by pointing to the other file while typing in a
formula. The link started out simply:
=[otherfile.xls]Sheet1!$A$1

After the first file is re-opened, the link gets changed to indicate the
full path name:
='C:\Documents and Settings\User\Desktop\[otherfile.xls]Sheet1'!$A$1

Then I copied both files to another volume (a flash memory card). When
opening the first file from the card, the link got changed again as one
would hope:
='F:\test\[otherfile.xls]Sheet1'!$A$1

Maybe Excel keeps track of how a link originally was defined in order to be
helpful in this way.