Registering a .eu domain even through an Estonian domain registrar (I use zone.ee) using an Estonian e-residency ID (which I have) still requires a presence in the EU[0] so this probably won't help UK residents.
0 - One of the proposals to expand the .eu domain is to permit any EU citizen living anywhere on the planet to register a .eu domain but it's not gone into effect yet.
Estonia's e-residency website lists several companies who can provide a legal, physical address in Estonia. Wouldn't that work for EU domain registration?
No, one would need to incorporate a company in Estonia
Yes, that's one of the features of e-residency. The same service providers offer both incorporation and a physical address.
Is that a problem? And does it have to be a company, or can it also be a foundation or something?
The naming is a bit misleading, e-residency provides absolutely no residency, it's a convenient way to digitally authenticate yourself as a natural person and sign documents digitally in an eIDAS-compatible framework.