Romania apparently. My country (Germany) isn't known for its easy to navigate bureaucracy but even here getting an EU VAT ID was trivial. Certainly easier than most of the other parts involved in starting a (legal) business. I think it was literally one of the documents they gave me to sign when I registered my company.

EDIT: I looked it up. It's literally just something you get to check off on the tax registration form for the company. Alternatively there's an online form (imagine that!) for existing companies. Impressively, there's no fax machine involved at any point.