There is no restriction on cookies not storing any personal identifiable information. The Munchkin ID falls within that category.
Furthermore, companies using Marketo can honour user preferences through Admin - Munchkin - “Do Not Track” Browser Request
The general rule is adding a popup giving users the option to accept the cookie.
The EU legislation is a broad framework. Member States can enforce more strict rules. Austria implemented the most demanding legislation; Finland is among the most relaxed. Austria maintains lists of opt-outs at national level. All companies targeting Austrian email addresses (ending in .at) must adhere to that list.
Marketing Automation and the European Privacy Laws