One of the most underrated pets I've found (Or least represented in Battle Pets PvP, at least) would be the Frostwolf Ghostpup. I just managed to snag one a few days ago while I was doing Archaeology on my Combat Rogue, and the sheer diversity of its skillset is astounding. It can be a really strong team healer, it can fit very well in Darkness teams (Especially with the Frostfur Rat because of Refuge), or it can even pair up nicely with Nexus Whelplings to nullify the stunning portion of Ghostly Bite. It's become such a favorite of mine that I selected it as my avatar here!
Corefire Imps, Infinite Whelplings, and P/P Spineclaw Crabs also don't get nearly enough credit. I've had many a cringe-worthy fight in PvP that ended with the Infinite Whelpling's Sleeping Gas completely locking down my opponent's pet (Leading to me retiring it), the Corefire Imp being a Humanoid goes very well with Immolation, and the P/P Spineclaw Crab is a monstrous Aquatic pet. Its Blood in the Water hits like a truck, and Healing Wave can restore a massive amount of health.
@Lio: Agreed on the Frostwolf Pup! Maul still makes me shudder in remembrance of all the times people ran an Electrified Razortooth, a squirrel, and the Curious Wolvar Pup and made my team cry uncle. The fact the Pup has Howl on top of it means it should be an outright dangerous Beast Pet. Here's hoping I'll be able to nab one soon to keep my Ghostpup company!