There was a change made to the WoW game mechanics a long time ago, perhaps before I even started playing back in late vanilla. The change was a statistical modifier for quest items, preventing players from having to farm for excessive stretches of time before finding their quest items. Basically, every time a player killed a mob that didn't drop the item they were looking for, the odds of the player finding the item on the next mob they killed was increased until the item finally dropped. Simple solution to an aggravating issue.
I realized that there is no such modifier affecting pet battles. If you want to capture a specific breed or a rare pet, you will have to farm until you find it, with only the pure statistical odds helping (or hurting) you. Some players claim the game was "better" or "more difficult" back when this was the case for quest items. I don't know if I agree, but I know that the harder you have to work at something, generally, the more rewarding achieving your goal feels. Hence, I like the fact that you never know when you'll find the pet that you're searching for - it adds a flare of hardcore-ness to pet collecting