I just tried to go through this process on my wife's brand new emachines
(amd64) machine.
The sticker was on the back of the machine, and quite small.
I did my best to read the code and enter it correctly, but it wasn't
accepted. I then filled in the brand and purchase location details, and got
codes allowing the validation to occur.
So--look on the back and sides of the machine. and have plenty of light and
your reading glasses handy.
I've seen the kind of problem I have only twice in about 48 machines I've
been though this process on--and I'm not sure whether its my vision, or some
flaw in Microsoft's process of tracking OEM PID's--the machine IS
validated--but it took a bit more work that most do.