WOOOOOOOOOOOOHHHHHHHHHHOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO
I went back to the store again and demanded to speak to the manager who again said that I had to contact Microsoft. So I phoned them from my mobile while he was there and then put them onto speaker as they confirmed that the key was not a proper licence for a home user and to tell the store that they have sold a wrong licence, and they would send a certificate confirming that.
I also told him about my complaint to Trading Standards (and lied saying they think that the store might be deliberately selling illegal software) and will be investigating for that.
The manager then decided to give me a different copy and to take it up with MS through their wholesaler. I just put the new code in AND IT WORKS

I took some pictures of the bad disk and packaging but I don't know howto attach them on here. It looks 100% identical to the one I have replaced it with. So weird.