Rotom-W has proved to be VERY popular on Random Matchup, usually finding one on every other team, if not every team per playing session. I use one myself also, it works very well with its STAB's and is REALLY useful in alot of situations. This is the set I use, it may look odd but it works:
Rotom-W @ Life Orb/Leftovers
Timid
252SpA/252Spe/4HP
Levitate
~Thunder
~Hydro Pump
~Pain Split
~Will-o-Wisp
How I play it is, I use it with Zoroark so it convinces Ice/Grass types to stay in while I Flamethrower them, but when this gets into play, I try to lure out high-HP Pokes (Like Suicune) and Pain Split them when I reach low HP (My max HP is 135 or so at lv50, meaning Pain Split heals me completely and deals a lot of damage to high-HP Pokes) and I'm usually fast enough to do so. Thunder/Hydro Pump are both risky, I'm considering replacing Thunder with T-Bolt for a reliable attack when something has like 5 HP left, as Wisp/Pump/Thunder missing in a time like that is usually fatal for Rotom. I find this is a good "counter" to Starmie, as I can switch in, Pain Split, then Thunder the next turn for the KO.