First, each EU country has its own laws about VAT and how and when they apply; it is meaningless to talk as if the EU were an entity that charges taxes.
Here is a link from the UK. The law on the additional rules for electronically supplied services is in the VAT Act Schedule 4A paragraph 9. To simplify things, I will restrict the rest of the answer just to the UK.
... the place of supply of the electronically supplied services is where their effective use and enjoyment takes place. Where this is the UK, the services are subject to UK VAT.
Specifics
Are they required to pay VAT?
Yes
Do they have to register under the MOSS system?
Yes
Is it their duty to make sure their customers come from EU?
They have to collect the right taxes for each country in the EU (and the world for that matter).
What if they didn't know this?
Too bad; its their duty to know the law.
And ultimately how will EU enforce this, if they do not register for VAT and pay? The company is outside their jurisdiction.
In what way is a company doing business in the UK outside the UK's jurisdiction?
Ultimately, if they have no assets in the UK it may be difficult for the UK to enforce any collection. If they were using, say, PayPal and PayPal received a garnishee order from a UK court, I am reasonably certain they would enforce it.
Does EU even have the right to tell nonEU company to pay EU taxes? The company operates online and purchases are done on nonEU servers thus contracts are made outside EU.
Its called sovereignty: a country can say where and when its laws apply anywhere in the world. It may lack the power to enforce them but it can certainly make them applicable.
In any event, these contracts are made in the EU - at least one party to the contract is located there.
