rmeakins: I've read that the fishing quests have a higher chance of yielding the special items after doing more of them, so keeping at it is definitely the way to go. I was pretty relieved when I finally got the last piece after 70 or so quests.
That wouldn't surprise me. Seems like I'm getting a Tackle Box, Fishing Radio, Earring, etc. about every third or fourth quest reward. Seems I've misplaced the Angler Hat since reward came ages ago.
rmeakins: The Lost Girl is also pretty annoying to find. She's also much more likely to spawn in pre-hardmode worlds apparently. A good way is to set up some kind of farm like this:
http://imgur.com/a/tmvId Here's a discussion about the farm:
https://www.reddit.com/r/Terraria/comments/1ra2y1/fully_afk_nymph_farm/
Haven't tried much farming yet (only a glowing mushroom, uh, room) but this might be one to try. Supposed to be a 50/50 chance to get the metal detector from her, and I've already beaten her six times. She's being tight with that drop. : )
Edit: the Angler just coughed up the Sextant so that leaves the Metal Detector. Could bring one in from the other world, but nah. Gotta earn that sucker fair and square.