They are however required by law to allow other app stores to function. This new licensing cost is a bald faced attempt to make other app stores nonviable. I'd be highly surprised if the EU is okay with that.
Edit: Seems I misunderstood, I just re-read the relevant section:
>iOS apps distributed from the App Store and/or an alternative app marketplace will pay €0.50 for each first annual install per year over a 1 million threshold.
The fact that they are charging money for apps installed from non-App Store sources is ludicrous to me, if they aren't running the store, then they don't get to collect fees on it, imo.