http://www.microsoft.com/japan/customer/infokb/Search.aspx?lp=40...
マイクロソフト カスタマーインフォメーションセンター - InfoKB(よくいただくご質問)
メディアの紛失(もしくは破損という扱い)で有償になると思いますが対応してもらえます。
ちなみに、WindowsXPのメディアはメーカ製PCに付属していたものですか?その場合はメーカサポートに電話しそこで相談するのが先になります。
WindowsXPのパッケージの場合は、さきに上記URLへの問い合わせとなります。
ありがとうございました。