It's not impossible to beat Gengar... I only played against it once at a Premier Tournament so I don't have much room to talk (I won it), but if you play like 2 Devoluters you can catch 'em off Guard (Pun intended). This allows you to get a prize ahead, so even if they hit the rest of their Fainting Spells you literally win if they don't take another prize off of something else. Just watch for Relicanth, or let them play down the first BTS. If you get them 50 HP or below, don't be afraid to drop a Sableye and KO them if you can switch out. This saves your resources, and you hardly lose much if they KO Sableye.
But anyways, Rogue Archetype played against like ALL Gengars at Nats and won them all. Hopefully he sees this thread, so he can share his secret... lol.
EDIT: R_A beat me to it, lol.