Maybe RNG affects much in how painful it will be.
Like some fishes are quite common but others not.
I spent 30+ minutes kicksledding, trying different lures and fish spots all around and drilling holes in ice etc. and ended up abandoning the quest because I just couldn't find the fish.
Just because you had luck and it asked only for common fishes doesn't mean that others had such luck.
RNG in things like this sucks, solution proposed in OP would be a good solution to greatly reduce the likelihood of getting some fish that is impossible to find.