Can you post back a camera snap of the COA sticker or type out everything on the sticker except the actual numbers?
Is it a holographic sticker similar to COA stickers you may have seen before?
It's possible it's not MS but the manufacturer's S/N or other identifiers.
Do you have a Recovery Partition on the HD, or Recovery disks you made or received - as these should auto-activate.