Illidari Masters: Madam Viciosa

This master tamer is new in 7.2 and is active through a world quest. See Lazey's comment for more detail, I also recommend watching the linked video to find Madame Viciosa, since her location on the map is currently incorrect (might be fixed when 7.2 goes live).

A possible strategy to beat her and carry a pet below, as well as on Xu-Fu's guides:

1. 
   
2. Level 10+ pet
3. 
   
4. Unborn Val'kyr (1 2 1)
5. 
   
6. Mechanical Pandaren Dragonling (1 2 2)
7. 
   

Strategy:
Pass with your level pet, it's swapped out.
Curse of Doom, Shadow Slash, Shadow Slash, Haunt
Bring in your Mechanical Pandaren Dragonling
Decoy, Breath until the first two enemy pets are dead
When Seduction enters: Thunderbolt, Breath until MPD is down, then Shadow Slash with your Val'kyr to the end. Win!

[Leveling Pet: must have >800 health (50% more health required if dragonkin or flying); I used level 15 roach with ~1000 health
[npc=63001] (2,2,1) - breed: health & speed (alternate pets with the same moves found here)
[npc=62621] (2,2,1) - breed: guardian (alternate pets with the same moves found here)

Ensure your pets are in the slot positions as listed above.
Regarding the leveling pet: if you take crit damage in round 1, you will need to watch your leveling pet when fighting Rover to ensure the AOE does not kill it. If your leveling pet dies to round 1 crit plus Rover AOE, simply restart the fight and try again - or grab a leveling pet with more health.

vs. [npc=117982]

• Start with leveling pet
• 
  
• Attack or pass - either way this pet is swapped for your next slot ([npc=63001])
• 
  
• [pet-ability=310]
• 
  
• [pet-ability=449] x3
• 
  
• [pet-ability=564] ([pet-ability=466] misses)
• 
  
• [pet-ability=310]
• 
  
• [pet-ability=564] > [pet-ability=449] until opponent dies

vs. [npc=117983]

• Swap to [npc=62621]
• 
  
• [pet-ability=172]
• 
  
• [pet-ability=179]
• 
  
• [pet-ability=501] until opponent dies

vs. [npc=117985]

• swap to [npc=63001]
• 
  
• [pet-ability=310]
• 
  
• [pet-ability=449] x2 (critters are immune to stun, so [pet-ability=772] does nothing)
• 
  
• [pet-ability=564] ([pet-ability=218] misses)
• 
  
• [pet-ability=310]
• 
  
• [pet-ability=564] > [pet-ability=449] until opponent dies
• 
  
• If [npc=63001] dies before [npc=117985], then bring [npc=62621] back in
• 
  
• If [pet-ability=172] weather effect is still up, use [pet-ability=179], otherwise, use [pet-ability=172]
• 
  
• [pet-ability=179] > [pet-ability=501] until opponent dies

Both of my pets were level 25 & rare quality. I used the listed breeds and have not tested using other ones. Based on my testing of the fight and the available breeds for the pets used, I don't think breed will make a difference for this fight. Both pets I used are easily capturable at high levels, so hopefully this strat is helpful.

One of the new pet battles on the Broken Shore.

Selected team:
Level Pet (720+ hp, 550+ hp as [pet-ability=237], 615+ hp as [pet-ability=244], 870+ hp as [pet-ability=239], 930+ hp as [pet-ability=245])
[npc=68659] - 1/2/1
[npc=45340] - 2/1/x (maybe even any [pet-ability=242] pet with [pet-ability=648])

Level Pet
01: gets swapped by [pet-ability=466]

[npc=68659]
02: [pet-ability=436]
03: [pet-ability=406]
04: [pet-ability=406]
05: [pet-ability=406]
06: [pet-ability=406]
07: [pet-ability=490]
08: [pet-ability=406] - [npc=117982] dies, [npc=117983] comes in
09: [pet-ability=436]
10: [pet-ability=406]
11: [pet-ability=406]
12: [pet-ability=406]
13: [pet-ability=406]
14: [pet-ability=406] - [npc=117983] dies, [npc=117985] comes in
15: [pet-ability=490] - to block [pet-ability=218]
16: [pet-ability=406] - you get charmed by [pet-ability=772] before attacking
17: pass - [npc=68659] dies

[npc=45340]
[pet-ability=648] till [npc=117985] is dead (use [pet-ability=611] if needed)

I tried to use pretty common pets for this, to make sure you guys can easily duplicate my strategy. As for the level pets: I tried to minimize their dmg taken by using [pet-ability=453] at first, but the RNG went crazy on me in terms of misses, so I went for the rather safe [pet-ability=436]. The numbers mentioned above for your level pets are a little higher than needed, but they can still be too low if [pet-ability=668] crits. Also it can be quite annoying if [npc=117982] crits too often, so your [npc=68659] possibly dies to either him or [npc=117983]. In that case you might just forfeit and start over again.

Please let me know if you were successful with any other pet with [pet-ability=648] and if so, which one you used. If you're experiencing major problems executing this strategy, let me know where you got stuck so I can review/alter this strategy.