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.
In Portugal you can buy and use a prepaid sim card without showing your ID or giving away any personal information. On the other hand buying credit is done via the bank, so you only have a few euros to spend before losing anonymity.
You lose anonimity in a very short time if you either:
1- Use the new "anonymous" sim card with a phone you already own and used with other sim card (IMEI matching).
2- Use a new phone with the new sim card but let it connect through your home WiFi network (IP tracking).
3- Use a new sim card and a new phone, but carry the new phone around with your main phone so that they find your second phone and number just by looking in the carrier(s) database(s) if there are any matches to the tower areas the first phone connects to.
You can buy a SIM card in a vending machine in at least airports in Denmark and the UK.