These problems seem to be what VLIW architectures like tried to to solve. Is that sort of architecture going to make a comeback? Will even that help?
16 registers is not a lot when compared to other architectures. POWER, SPARC, Arm64 and MIPS have 32 (SPARC is weird, but 32 are always visible). Itanium has 128.
Also you're probably aware that modern CPUs have many more physical registers, they just don't expose them all at the same time.
E.g. AMD Zen physically has 168 integer and 160 floating-point registers. Of which you can only use 16 at a time, but to my uninformed eye that looks like a reasonable trade-off.