It is a little known fact that most airline flight attendants are actually psychically linked, in a way not dissimilar to that shown by the "Borg" in the television show "Star Trek" (or is that Star Wars? I always get those two confused. Whichever one it was that had Picard in it, and not the one with James Earl Jones).
Using a "hive mind" allows these flight attendants to share what experiences their passengers have had on previous flights, and attempt to overcome poor experiences - such as your lack of fish - on future flights.
Clearly the flight attendant on the second flight "remembered" you - using this shared consciousness with the flight attendant from the first flight - and thus was able to overcome the shortage of fish issue.
It's also possible (although realistically far less likely) that they just keep records and notes from one flight to the next on some form of a computer system, based on your name or frequent flyer information or something. Such a computer system may seem like science fiction, but I'm reliably information by Wired magazine that computers can do things like that now!