> Perhaps their fishing tools were made from materials which are less
> prone to become fossilized than other artifacts?

The cat fish can apparently be caught by spear. At Wadi Kubbaniya c
16.000-15 000 BC (18000 BP) The Nile flowed at higher levels than today.
at this site catfish and other fish bones are found along with waterfowl
It is thought that the catfish swam into shallows in the flooding and
were caught in the receding waters, so I expect they could be caught by
hand or net, too

18 000 BP was the high of the glaciation in Western Europe.

The reference which goes with this is <Loaves and Fishes: The prehistory
of Wadi Kubanniya.> Wendorf F, Schild R and A Close. Dallas:  Southern
Methodist Univ.1980
The same techniques would be useful for atlantic salmon which were
caught in the ice free salmon rivers of SW Europe in the same period.

None of this stuff is any of my own research, by the way.  Certain list
members seem to prefer a little anonymity and so I'm happy to oblige by
reposting for them.