In order to handle Side-by-Side installations, you will have to consider unique install paths for each version or unique names for the common files. Take the MSVC Runtime as an example. They install to the same location but the files are named differently.
Naming files differently might not be something you can support since you already shipped something and it sounds like your users have some expectations at this point. It is hard to change expectations.
Another suggestion is to always install the runtime pieces from older releases. This causes your installer to grow with each release but it does eliminate multiple entries in add/remove. Without changing the names of the files, you would need to add unique folder names.
I have an installer that supports many versions back. It consists of 3 runtime dlls (unmanaged).
These files get their name changed with each version. myproduct_1.0.dll, myproduct_2.0.dll and so on.
Libs and header files to match each version are also installed.
Because they are unmanaged, they are also in the PATH. So because I have unique names, I only have to make 1 PATH edit too.
In short, it depends on your specific goals, requirements, and willingness for your customers and dev team to modify their expectations.
My dev team came up with this scheme because the customer wanted it. Before this, new versions would overwrite the old one and there was no way to go back. The customer had to make some internal changes in order to support the feature they requested.