It's not as outlandish as you may think.
Tesla has already said that it expects batteries to cost $100/KWh by 2020. Although that may be a little optimistic, I don't think it's off by more than 2, maybe 3 years. By 2020 batteries could cost around $70/KWh, after which Li-Ion batteries at least, will probably stagnate, as it's close to raw material cost, but I expect some new type of batteries to emerge by then with potential for higher density/$.
But let's say batteries will only be $100/KWh by 2025. There was a recent report [1] saying that at $150/KWh, and considering charging and maintenance costs, which are about 1/3 that of a normal car, EVs should be competitive. So you may pay a little more for an EV upfront, but overall it should be very competitive.
I expect by 2025 we'll see 15,000 euro cars with 200+ mile ranges as well, possibly even from Tesla, but even more likely from Renault, Nissan, Hyundai, etc.
But beyond all of this, I suspect one of the reasons why Norway set up this deadline is because just like Denmark, it actually wants fewer cars on the road. So such a law is very compatible with that goal as well, although in a more indirect way. If you must have a (new) car after 2025, then it better be an EV. I think it makes a lot of sense, and I think we'll see a few more countries establish such goals by 2025, or 2030, as well.
[1] - http://www.techinsider.io/electric-vehicle-battery-cost-decr...