I literally Googled the sh*t out of this question and did not get anywhere, so here’s a quick tip to the unfortunate souls who like me, lost their Windows CD but still have the license key. It’s so frustrating to have the key but not be able to install the correct version of Windows, especially an outdated version of Windows that is not available for download anywhere (legally). In case you were wondering, there is no option anywhere on the Microsoft website that allows you to order the CD.
Call to Microsoft Australia at 13 20 58, option 4. It’s actually the wrong option because this gets you into their Partner Program instead, but explain what you need and the person will redirect you accordingly. The main thing to note here: you are looking for “replacement media“.
The process turned out to be surprisingly painless. I had to provide my name, email address, phone number and my Windows XP Home license key for the order, and that was it. The order will be coming through email, so I’ll be looking forward to my new CD soon – I hope.