First, Apple did nothing illegal. There is no wrong doing here. They pay tax in every country they owe tax. Period.
Second, perhaps it's not Apple that's the problem? Perhaps it's the tax that is the problem.
If you have mega corps building entities outside its main jurisdiction to avoid the main jurisdictions tax burden, perhaps you need to revamp your insane tax code. Hmm?
There are hundreds of different ways to tax. Taxing corporate profit is controversial because it's very hard to determine what exactly constitutes profit and for multinational firms like Apple deciding in what jurisdiction profit occurs is highly arbitrary (your iPhone has parts from half a dozen countries). The most logical conclusion is to simply get rid of corporate tax and make up the shortfall by increasing other taxes. Several countries already do this, countries like the US that stubbornly persist in trying to levy such arbitrary taxes will simply chase away international business.
The cost of goods inside airports would be significantly lower if business travelers couldn't just expense everything they buy. As long as it's max 1/3rd of the usual food allowance businesses can charge that amount and be assured that business travelers will pay.
If you take away corporate taxes then "expensing" will go away entirely. Along with all those receipts you have to save and the entire industries and businesses that profit from it (e.g. fake receipt producers, Concur, etc).
Wealthy individuals wouldn't be able to expense their purchases through subsidiary corporations anymore which would necessitate collection via sales tax. If you think that's an awful lot like the Fair Tax system you're not far off.
I'm actually not an advocate of the Fair Tax or even a Federal-level sales tax because it would be very regressive: Vastly unfair to the bottom 50% of society. Having said that, if you abolish corporate taxes it's one of the only ways to obtain tax revenue.
Because that is what abolishing corporate profit tax comes down to. The only substantial tax most states have are consumer taxes, and we all know that these taxes disproportionately hurt people that are already poor.
As companies benefit from this incentive, they lobby to keep it around. Very successfully.
So no, revamping the US tax code is (quite obviously) not an answer to Apple not paying tax in the EU. Having enforced taxation rules that prevent the race to the bottom is. Unfortunately taxation is not in the remit of the EU at the moment. Hence the back door approach through "unfair tax benefits".
We don't need trade deals that harmonize things so countries can, we really need tax deals that harmonize, or at least put minimum standards on taxes.
Why wouldn't something like that fly? Well because if the impression European observers have gotten over the last years is correct, then Apple et.al. basically own US policy on that point, to such a degree that the US actually threatened the Commission against ruling as it did.
So no, Apple did nothing illegal, but what is happening is clearly wrong, and Apple is lobbying to keep it that way. Heavily and successfully. And that is wrong.
For an example of an ethical stance a corporation could take here: IBM was, at least for a while, lobbying for abolishing software patents while at the same time owning a massive amount of them and registering new ones.
A structural fix would be to work towards making the US (and the EU, and all other) political system more resilient to lobbying pressure from powerful corporations.
But that is about as hard a problem as you are likely to find.
I don't see the EU giving Microsoft grief. It'd seem they're paying EU taxes differently than Apple.
Apple paid 0.0005% tax on its European profita. There is no non-'insane' tax code that could compete with that.