I really enjoy pet battles, but WoW has trained me to not "waste" my playtime on activities which do not provide any character progression [or at least high gold per hour]. I was joking when I first suggested providing Valor Points for max-level pet battle wins, but I've actually come to the opinion that it would be a really good reward to add to the system.
At, say, six minutes per battle and assuming average skill [ie 50% win rate], five VP per pet battle win would still be worse Valor/minute on average than daily quests, so it wouldn't break the system. It would be akin to XP in levelling BGs-- a small bonus to the activity so that your progression doesn't completely stagnate if that's what you spend all your playtime doing. And at around 20 hours playtime to cap Valor this way, I'm sure it would satisfy Blizzard's "give the player plenty to do" policy on everything being a huge grind.