歯切れのよい回答でなく心苦しいところですが
うちでも同様の現象が起きて起きています。OSX10.6.8です。
そして隣人の10.5.8ではリンクが切れません。
おそらくそんなところかと。。

これかな。
環境設定の、添付画像で囲んであるチェック2つオンにしてみて、どうでしょう。
手元の簡単すぎるテストではリンク切れは起きませんでした。
で、隣人の10.5.8マシンでは現状こうなってました。OS関係ないですねすいません。

（z-）様ありがとうございます。
環境設定のチェックをオン・オフ両方試してみましたが、リンクは切れてしまいます。
もう少し試してみました。
Winで新規作成したファイルはリンク切れがおきなかった
Macで新規作成したファイルはリンク切れがおきた
Macで新規作成し、Winで編集してもファイルはリンク切れがおきる

どうもMac固有の問題っぽいです。

> Indesignは相対パスでリンクは管理されていると認識しているのですが、CS4のみこのような仕様なのでしょうか。

一概に相対パスとは言いきれません。OSやバージョンによらず稀に不可解な現象がおきます。
これを解消するには別のマシンにコピーする前にパッケージして、パッケージしたフォルダごと渡すのが良いかと。
もちろん、リンクしたIllustratorに画像をリンク配置している場合などもあるでしょうからその点にも注意が必要ですが。