You can believe or not, but my Unborn Val'kyr was caught during a casual leveling in Northrend.
I knew that she's quite a rare, but hadn't known the whole mechanism.
So I didn't even consider how lucky I was that she was also naturally rare!
I've also caught a wild rare Minfernal -- I still do have a screenshot -- but that was camped, of course. That took about two months, once or two a week.
EDIT: Joined from the l25 paladin to Moonfang group for lulz and for ressing people from outside the combat.
And now I have another [pet]Moon Moon[/pet].

@Darolyn, how dare you!
I have compiled community knowledge & data about pet battle abilities!
https://www.warcraftpets.com/community/forum/viewtopic.php?f=3&t=19507