VirtualBox 3.1.6 で作成した VDI ファイルを別のマシンで実行している VirtualBox 4.32 にインポートしようとしたため、上記のソリューションはいずれも機能しませんでした。このファイルは独立したファイルであり、別のVDIとのリンクはありません。エラーが出続けていました。
Parent medium with UUID {a9dccef3-45f8-45ff-835e-a2b6e7279bac} of the medium
'c:\Disks\Windows.2003.R2.Enterprise.SQL.Express.192.168.56.222.Trusted.vdi'
is not found in the media registry
VirtualBox 3.1.6 で同じ vdi をインポートしてから、VBoxManage clonehd を使用してエラーを取り除くことができるかどうか確認してみましたが、これもうまくいきませんでした。
<HardDisk uuid="{43ea34ba-6d72-413e-8b37-32f475927ace}" location="C:/Disks/Windows.2003.R2.Enterprise.SQL.Express.192.168.56.222.Trusted.vdi" format="VDI" type="Normal"/>
(uuidはVirtualBox 3.1.6のVBoxManage showvhinfoを使って取得しました)
これでようやく問題が解決しました。
このメモが同じ問題に遭遇した方の参考になれば幸いです。