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.
If you want your CPU to run fast, you have to pipeline instructions and you need caches that can run at full CPU speed. It's easy to design a CPU without all the complexity, but it will be slow. No one knows how to do both simple and fast. It's probably impossible.