Try try again with microsoft, eventually you will get someone that will allow you to redownload it.
You should have repair tickets or warranty receipts or something to prove that you had to send it in for warranty, and you can offer to email that to ms to prove it.
When you do get another downlod, BACK IT UP.