It seems that to work for a company in (European) country A while living in a (European) country B, the two options that do not involve an excessive amount of bureaucratic complications are working as a freelancer, or making use of an employer of record.
What are downsides and upsides from an employer point of view in hiring people in this form? What is generally the fastest and easiest way to set up?
Some context: as a fresh graduate I have zero leverage to negotiate location flexibility (here and here). Better would be to demonstrate I am a valuable employee on site, then ask to go remote. I am trying to understand if it is just too much hassle for a company to say yes. I am concentrating this time on the bureaucratic side.