A problem that you could be experiencing also is that you have hav purchase the software legally but the store, possibly out of laziness, might have used a of-the-net key for install.
This is not that impossible as I have had a few machines come in from "a reputable dealer" where they have used a dodgy key but supplied the legit OEM slip and everything.
Check the installed CD-key using Magic Jellybean, and compare it against the one you have been supplied. If thier not a match, then you have been ripped. If they are, then you're right and Microsoft is messing around with you.