WoWDB

Can ONLY be caught during sand storms in Tanaris (and ONLY in Tanaris, not in Silithus).

The easiest way to catch one is to invest 1 hour to level a DK on a really low populated RP server, since the pets are account bound. Choose a PVE server, so you cannot be attacked by a higher level player while having a pet fight. Create a DK, get through the starting quest until you get to OG or SW, then simply take the flight point next to the Gaping Chasm.

With this toon farming other rare pets on this continent is also easy as hell. Especially the Minfernal ( Minfernal) can be caught with no other guy flying around. I got the Minfernal, this funny guy and all other rare pets with my DK. If you got some spare time just level to 60 and get yourself flight skill. But you won't need it at all, since all rare spawn points are nearby Flightpoints.

Addendum: Get yourself a map addon like SexyMap (http://www.curse.com/addons/wow/sexymap) where you can maximize the size of the minimap so you don't have overlapping pet trackers.

It took me about two weeks of camping to get this guy. I had four characters from different servers camped at both silithid areas in Tanaris and would log over to see if a sandstorm was up. I logged in during a number of in-progress sandstorms, but never seemed to be around at the start. A few things I found:

1. They do not spawn inside the tunnels (I felt silly asking this the first time, but I figured others might have the same question), only on the surface.
2. They do not respawn during the duration of the storm (others mentioned they do very slowly, but I've sat through an hour/two-hour storm with no greens paws).
3. You HAVE to be there at the start of the storm since only a few spawn at the start. (Edit: Maybe they now respawn during the duration of the storm, based on Funky303's experience. This would be AWESOME.)

I decided to stay on just a few minutes longer while I went to get ready for bed with no storm up - came back 5 minutes later with a storm and 3 green paws on my map (I was at Gaping Chasm). I caught my first one, and when the battle was finished, the other paws were already gone.

Well in my experience they can respawn.

I caught mine today. I logged in while the storm was already going on. I mindlessly attacked it with my 3x Lvl 25 pets and had a really bad luck of critting => first one down. It was the only green pawn, so I ran around the enteire Gaping Chasm, then went to the other area close to the Un'Goro crater, but same there. No green paw. I rode back to Gaping Chasm, and there was another green paw. This time I got it, and, lucky me, it also was a rare one. Please don't tap and fight all pets if you're huting them since you can use the Upgrade Stone from the Daily Pet Quest reward to upgrade it. I ported to SW and told everybody in /2 that there's a sandstorm in Tanaris. I got 2 happy answers of a successful catch back.