Been playing on both sides with basically identical bara deck, the decks I find solidly beating it maybe 50-65% when played correctly are Greyjoy-Tyrell and Greyjoy-Baratheon. These same decks I'm winning like 75% or more against non-baratheon factions, so if they can go 50-50 with bara and steam-roll non-bara, they could win tournaments just fine.
The lynchpin of the entire bara strat is the iron throne, because it lets you activate painted table.
Sometimes it's best to just leave Painted Table unscratched and focus entirely on Iron Throne advantage.
We Do Not Sow his throne (not hard at all for bara with 2-4 stealth) while you play your own throne Or while having Euron win a single mil or intrigue or pow and now all the Thrones are on your side of the board and Painted Table is near-impossible to activate. (Especially if he has to commit his strength to POW challenges for Red Keep or lack card draw engine entirely)
Your bara-fealty has 0x Put to the Torch so once GJ gets domination (which I field multiple Iron Throne for to resurrect dead people) instead of 3 free power swing in your favor, every turn 1 power is going to GJ for dom and 0 additional bonus power for Bara.
If the game drags out, you can Confiscation his 1x Lightbringer and now his deck has 1 source of Renown in the entire deck on Robert and you'll want to be pouring all your control on Rob so he doesn't get to use it much. Combine with stealing his dominance you should hit 15 first big time.
Fitting Tyrell characters onto Greyjoy's best gives better brute force than any fealty deck. Once you secure dom for greyjoy, the extra 2 sources of Renown should grind out a win.
Fitting Baratheon R'hllor package onto Greyjoy gives the full set of extra kneels and Seen in Flames. Seen-in-Flame that upcoming Melisandre or Robert or Stannis or any enemy trick card you don't want to deal with. Kneels combo amazingly well with Greyjoy because they get you unopposed challenges when needed (such as to destroy Iron Throne or Red Keep so you can steal them) and they nullify the big dudes in a fealty deck.
Last match I had Stannis+Lightbringer and Robert Baratheon+Bodyguard out with some other knelt stuff (thanks Stannis) and the enemy had Euron Greyjoy with Seal of the Hand (basically two 7-strength tricons with amazing ability) + Asha + Theon.
He uses False on Robert. Wins as many challenges as he wants.
Next turn he kneels Robert again, free reign of unopposed challenges with stealth + stealth + euron super stats + euron with free stand.
Greyjoy with no banner has a harder time. It has worse control and strength and trickery than r'hllor banner and doesn't necessarily win a long grindfest game that Randyll Tarly, Margaery and Knight of Flowers would swing over for GJ eventually.
That Bara deck is definitely a strong tier 1 deck, but I expect an equal number of tournament placement for strong Greyjoy-banner decks because they have the best answers to Bara, that are no less useful against non-Bara decks (I've never played a match where We Do Not Sow and Euron's anti-location stuff were definite dead draws against any faction)