I finally figured what was happening and fixed it.
Several years ago (around 13-14 when I joined the company) I was still a novice in Storefront. By the time I did some things in an odd way and one of them was that I created our custom packages not as 'topics' but as 'vectors' that are now a deprecated entity (it doesn't exist anymore in Multistore, as far as I know). I never managed to know exactly what were the 'vectors' but I suspect that it was a way to group similar products, like a subcategory. Anyway, it proved to be functional to create my custom pages so I simply used it and never looked back.
Time passed and we upgraded to newer SF versions through the years, and so the vectors table remained as a 'left over' in the DB. Curiously vectors packages are still supported by the latest version of Multistore regardless it is deprecated (for retrofit compatibility reasons I suppose).
Long story short my issue was exactly in the vectors table. There I found a long list with all my old packages and as I suspected the problematic links were there pointing to unexistent packages in our current system. Then it was just a matter of update the proper records and make them point to the correct packages and the issue vanished instantly. Of course I had to do this directly with SQL.
And why did I longed that much to figure this out? The reason is because although the vectors are still rendered they do NOT show up in the Admin so basically you won't see them anywhere, unless you know where to look (directly into a table that probably is not even documented nowadays). I only managed to figure it because I have created the vectors myself several years ago otherwise I hardly would find it. I just realized what was going on because the name of the links that started with "v-58" and "v-59" and I started thinking what the "v" standed for, and when I remembered that they were "v for vectors" I got immediately to the DB to see if there was a "vectors" table there and... bingo!
Anyway, it's all fixed now!