If you google for their name you will find lots of complaints about them.
1.The C of A - I would give MS a call and ask about that if I were you.
2. Product Key - yes you should have a product key - I would inform MS if I were you.
2. Apparently their site does say they ship from abroad.
3. Apparently they say they ship "as a gift" (which has to be below £34 I believe). Otherwise you should pay any import duty and they should have added VAT to your original invoice. Sounds illegal to me.
4. I doubt if it's a PCWorld special - but it could be a special MS offer, and not necessarily the same as bought in other places.