Have you looked at your adapter, I have ux31e ultrabook and it's windows product key was on the adapter block?
As hot as those bricks get from charging, I could only imagine a black sticker after a while from thermal transfer.
I called Toshiba on mine and was told it was in the UEFI Bios so no need to have it printed anywhere. I did do a re-install a month ago but used the built in recovery so no problems. If you got the Laptop w/o a OEM sticker, documentation or whatnot and it won't recover w/o a key then you might have to go the route of calling Asus or Microsoft like others have said.
Or, if you have return privileges (Within your product return window), exchange it for a new one and tell them it won't reinstall Windows 8. Most stores will chalk it up to hardware and send it back to factory. Who knows? You might have had a bad build in the first place that quality control missed when that worker responsible for loading the key into the machines was sick that day.