Hm, it took me about a week to update my entire collection to all-rare. It also helped getting the achievement related to number of pet battles won. I have been doing various stuff on the second monitor like reading feeds and stuff, but most of all, I tried not to overdo it -- if I was out of luck for some time, I just started doing something completely different (not related to WoW).
There will be cases when you will be cursing, not being able to find the right pet. What also helps is having some alts placed in strategic positions and switching between them to get certain hard-to-get pets. Also, don't fuss about not being able to get one or the other, because if you battle a lot, you'll end up with loads of excessive stones. For example I still have about 10 beasts and 10 flying pets (non-wild) to upgrade to rare, and I have dozens of excess stones for other kinds (yes, I do exchange them for flawless, but if I didn't bother with some hard to get non-beast and non-flying pets, I could have simply stoned them instead of spending hours trying to catch one).
My worst experiences with getting rare wild pets:
- The oozes in Hinterlands in the cave. They have a slow respawn rate and there's a limited number of them. Good to place an alt there and check once a day or so. Since they're magic, you can also skip catching a rare, and wait for excess stones.
- The rabbit in Hillsbrad, which supposedly only appears in Alterac area, but I never saw one as primary. Hundreds of battles trying to get one as secondary and rare, and finally managed. Kun-lai runt helped (rampage ability) with downing teams quickly, if there was no rare rabbit in them.
- Undercity cockroach took me quite a while as well, the trick is to kill all the critters, so best do it with a class that can AoE critters, e.g. mage (arcane explosion) or monk (the whirly spell). I did it with a monk. Took me 3-4 hours of killing critters before a rare roach spawned.
Surprisingly, I had very little problems with rare-weather pets. I caught the Tanaris one on first try when sandstorm appeared (!), and the STV one also took me a very short time. In both cases I had alts placed there and just checked for weather.
So, in general, if you do have alt characters, make sure to use them, and swap around not to get too bored. Patience is key here, but it's not as difficult as I expected, it took me much less time than getting PvP 1000 wins for the title -- now this is quite a drag, even with good teams ^^.