>And by that logic nothing in the Universe is anonymous, since it's deterministic and it doesn't lose information, so theoretically everything could be traced back to its origin.
Nowhere in there it says that information was lost. It just says that to reverse the process it requires introducing energy to the system and that the impossibility resides in that the changes occurred in an "not easily predictable". So it's a practical impossibility, not theoretical.
The Universe doesn't lose information. The one thing that made physicists believe for a moment that it did, was something about blackholes, but it was then proven to be wrong.
https://en.wikipedia.org/wiki/Irreversible_process
If a process is irreversible it means information was lost. And from the article, "All complex natural processes are irreversible".