A street around the corner from me in Frederiksberg is being converted from painted bike lanes to separated bike lanes, with a kerb/curb. I ride on this stretch almost every day and I've never felt like the stretch needed a physically separated lane, but I'm certainly pleased it is soon finished.
You can see in the photos how they place a kerb towards the street - we use long blocks of stone - and then the gap is filled in with asphalt to complete the safe, separated cyclo-deliciousness.
This is a sign straddle the bike lane at the top of the street reading "The building of cycle lanes will be completed November 2008."
In the new suburb of Ørestad - as with all new development - building bike lanes is a requirement. There are also separated lanes along the main road through the suburb, but here you also get a quieter route if you wish to use it.