Faulty MS Help Desk Support

How does one recover from faulty tech advise from MS help desk?

Scenario:

1. PC with preloaded OEM Windows XP Pro
2. After 3 hrs on phone, MS Help Desk advised to format HD and clean install W/XP.
3. Now that HD is formatted, cannot install XP due to OEM Recover version.

What can one do about this and license key?