Its tough. I don't believe there is a best spawn zone or time - its really just random. There's a good map of the best route to take for flying around to all the spawn points if you want to search that way.
I have a DK alt on a low-pop RP-PVP server that I have used for getting a lot of the rarer pets that are camped since those servers weren't CRZ'd (although I think that has changed recently). I'd recommend that for general rare pet acquiring purposes although it wasn't a big help with a Valk since I didn't have the gold nor the interest in leveling enough to get flying in Northrend. I did park it at one of the spawn points, but I ended up randomly coming across one on my main while flying through the zone to get another pet.
Every now and then someone posts on here that they've found a Valk and will hold it for someone, but its really just going to take time and some good RNG to get one yourself.