救済策についてはここを読んでみるといいですよ？

マイクロソフト、正規 Windows 推奨プログラム「Windows Genuine Advantage」の正式運用開始
http://www.microsoft.com/japan/presspass/detail.aspx?newsid=2348

無償で貰うのは困難と思われます

特選街ブログ: ところで、あなたのXPは正規版？
http://tokusengai.way-nifty.com/blog/2007/02/xp_a2c0.html

以下のページに説明があります

マイクロソフト、正規 Windows 推奨プログラム「Windows Genuine Advantage」の正式運用開始
http://www.microsoft.com/japan/presspass/detail.aspx?newsid=2348

こちらも参考にしてください(購入報告書の流れが分かります)

正規Windowsチェック、正式版に - 偽造Windowsは無償で正規版へ
http://journal.mycom.co.jp/news/2005/07/26/009.html

オークションで販売している場合、ＯＳは動作確認用として入れているだけの場合が多いのではないでしょうか？
（動作確認用として入れる行為については別の問題です。）

出品状況によりますが、ノートＰＣとして購入したのであればインストール用のCD類が付いてこなくても当然です。
正規ＯＳ付きとして購入したものがメディアの添付のない場合、または偽物であれば詐欺行為ですから出品者に代金返還請求するのが先。

無償・・は、かなり高いハードルを満たす必要がありますよ。
簡単に言うと正規品と見まがうような精巧なコピー品を提出することが最低でも必要。
CD-Rに焼いてマジックでXPなんて書いたものは認められません。
コピー品はWGA認証でコケるようになっているのでその際に表示されるWGA-Kitを購入して正規のXP_Professionalとして認識させるか（リカバリ用ＣＤは後日届きます）、MSのサポートが受けられないぶん安価になっているOEM版XPを購入するかです。
でも、XPのコピーを入れるほどのPCということは元々はWin98時代くらいのPCだと思うので、性能が低い関係上、無理してXP入れても期待するようなパフォーマンスは発揮できませんのでムリしてまでそのＰＣを買うのはどうかとも思いますね。