I don't get most of these posts. Starmie without Rapid Spin isn't even that good of a pokemon, definitely not OU material. She's OU just because of her spin. That's why I don't get the point of "countering her" if you cannot block the spin or at least guarantee the kill.
Enemy swaps in Starmie -> You swap in SDef Rotom-W as she spins -> opponent switches Starmie away. Here it doesn't even matter if Rotom-W is good against Starmie, she still got rid of the entry hazards.
For getting the kill, best options are CB Scizor and CB Tyrannitar, though Scizor needs to be wary of Hydro Pumps especially in the rain. Pursuit 1shots her, though she's faster so she can put a decent dent on both, which can be quite detrimental to the Tyranitar in weather wars.
Preventing the spin is tough because Starmie does well against the common spinblockers. I'd just stick to pursuits.
Also, if you're expecting a Choice Band for some reason(Say the team has both a Tentacruel and a Starmie), Starmie might carry Trick and in that case Blissey and SDef Rotom-W for example would be extremely risky to use against her.
I agree that spinblocking Starmie is needed when wanting to keep your hazards up- but I don't think that restricts the amount of counters Starmie has, nor do I think it is absolutely necessary when looking for counters.
Remember, we're countering offensive pokemon- which involves discussing pokemon that can take hits and reply back with powerful attacks or outspeed and OHKO. Starmie's ability to spin is completely unrelated with the pokemon that can counter it- as RSpin is a support move, and counters are meant to be able to shrug off offensive moves. (this is why we're not countering pokemon like Blissey or Forretress.) We're looking at Starmie's offensive side here, not its Rapid Spin.
Besides, there are really no Pokemon that can successfully counter Starmie if they need to be able to spin block as well- bar SBall SpDef Jelli and some Uber pokemon.
And Rotom is a great counter; yes your opponent might spin but you will immediately get a lot of momentum by either KO'ing Starmie with VSwitch or scouting the switch in.