When you deliver an InDesign document including images it is not always apparent if the images will be found automatically on the receiving end or not. Bob Bringhurst explains the rules of the search algorithm.
In short: InDesign always stores the entire path to the document as well as to the linked files. First it tries to find linked files under exactly that stored path. Thus even a renaming of a folder on your own computer triggers the search algorithm.
If the file can’t be found, InDesign looks in the folder of the document. (This BTW is the simplest way to ensure that your files will be found if you are unsure about relinking).
Next it will look into subfolders of the document folder, if the files originally where saved in subfolders. The same subfoldernames are tried.
Lastly it looks into the subfolders of the document folder’s parent folder. This is useful in case the document itself was moved into a subfolder.
An example: Assuming the linked image was c:\links\graphics\my.jpg and the document when opened is /osx/projects/p1/doc.indd. Then the image will be searched for in these locations and in this order: