I don't really know exactly since when this happen. I think since I updated to Ubuntu 20.04.
I have used Fish since a long time, and earlier via Linuxbrew to get a more recent version.
So I assume this is some mixup of the configs or formats.
How do I debug this? I don't get any error. When I press up-arrow in a new shell, it will print me some very old entries (I don't remember from when, but some years old I think).
Strangely, even removing ~/.config/fish
did not resolve this. It even still has the old history. I actually have no idea where it gets this history from...