Ok, to explain that, you need to know what color profiles do and how your monitor displays colors. I will keep it simple and will not cover all details of color management, if you want to know more, simply search the web.
1. Your Computer
Your computer is the only one how knows the exact color of your image.
The color is defined by numeric values in a reference colorspace like Lab.
Sadly your computer needs an output device to show the color to you.
2. The output device
The output device could be a printer, a beamer or a monitor. To keep it simple lets look at the monitor: Your monitor can not display the full reference colorspace; it has its own smaller colorspace. Your monitor needs some kind of translation between the reference colorspace, your computer is using and its own colorspace. This is where color profiles come in play
3. The color profile
The color profile knows how colors are displayed on your output device and can translate colors from your reference colorspace to your output devices colorspace.
So lets combine all of that:
Lets say your monitor has a red color cast. Your color profile knows the exact values of the colorcast and can add blues to make the output of your monitor appear neutral. This way the colors of your monitor match the intended colors, even though your monitor has a colorcast.
This means all of your output devices have their own color profiles which are intended for use with their exact output devices and nothing else.
So, what color profiles do is: They alter the colors to appear correct on the output device it is made for.
Now, to your problem:
I tried every possible color setting / profile combination, but I couldn't find the right color profile that produces those nice blueish colors
Usually I would say the color profile fits to a device that you had at the time you converted the image and since you are not using it anymore, you do not have the color profile anymore.
However in this case, I think you installed, lets call it a helper profile.
If your document does not have a color profile attached, you should assign the one it uses. To do that, you do not simply click on Profile and hit enter. You have to change it to the profile, which is used by the document.
The "You always need to modify this tag" should remind you to always do exactly that, change the profile to the right one.
The blue color cast probably is an extra to show you it is wrong. It modifies the colors in a way, it is easy to tell, that there is something wrong with the profile. This profile is a reminder to always change this setting if you need to assign a color profile.
Now, after all these years, I really wonder how to find (or make) a valid color profile that produces this nice color effect.
This is completely the wrong approach to the problem. You now know what color profiles are used for, so what you really want to do is to change the original colors of your image – the color values in your file.
You can do that with adjustments in photoshop. If you use curves, for example, you can reproduce those colors exactly how you like.
If you have altered the colors in your document and are using a correct color profile, all those changes in color are accurately shown on other output devices too (if calibrated).
Rescue the old images
Since you do not have the old color profile anymore, no one knows how to properly display the colors. The best thing you can do is to assign a reference colorspace that works best with the image (try AdobeRGB or sRGB) and then adjust the colors by using Photoshops adjustments to your desired output.
