Last time I was there in Denmark I had to provide a CPR number to enable the SIM card. For the non-danish people the CPR number is basically your lifetime number for everything from social security, to tax, payroll, etc.
Because I've seen SIM cards that can be bought in supermarkets in another country, but then you need to show your ID to an operator over Skype to activate it.
You can buy a SIM card in a vending machine in at least airports in Denmark and the UK.