I honestly thought that Starmie had a very high shaft.
Considering that it was one of the most (and probably still is) overused pokemon in the games with its versatility and speed (games aren't the same as anime, but generally some properties retain, like it being able to use Thunderbolt)
Misty's Starmie lost to Pidgeotto for the most part at Cerulean City. (ep 8)
Misty's Starmie's core was broken by a spinning Graveler used by Gizelle (ep 11)
Misty's Starmie's core was broken by Raticate's Super Fang. (SS Anne)
Misty's Starmie lost to Jesse getting whacked by a giant hammer. (Bye Bye Butterfree) This probably isn't really a loss but a beatdown. It was one good whack too (and I wonder why Jesse never used that strategy again).
Marina(Tsubaki)'s Starmie lost to Golduck's Hyper Beam, even with a Light Screen up (or was that Ice Beam?) (Marina/Tsubaki vs Misty/Kasumi)
Rudy's Starmie lost to Squirtle's Hydro Pump followed by a Skull Bash.
Starmie also feared Arbok when it was terrorizing the aquarium in that Misty Mermaid episode (it didn't necessary lose, but it showed extreme fear for something that technically can't show expression and it sweatdrops.)
I'm sure there were other cases but I can rarely recall wins. It wasn't get many victories (if any) from typical Team Rocket wins. Misty's in particular was left in the gym, and Staryu was the starfish that was used the most.
I honestly can't think of the wins it had. I really can't! Unlike Ash's Torkoal, OTHER trainers lost with Starmie too (and the examples I put, Starmie did NOT have a "prior victory" within the same battle either! For the case of Torkoal you could at least say Flannery nearly sweeped Ash's team with it.)
Starmie is EXTREMELY useful in the games. In the anime it doesn't seem as particularly useful.
I'm quite sure Starmie would qualify for this category. However, most likely it is not perceived as a "tough pokemon" within the anime. In the game technically it's versatile and quick, not power loaded (it's more like it's well rounded). Of course the moveset it has in the anime is quite small, whereas the moveset it has in the game is extremely big for a water type (or a psychic type for that matter). In the game, there's a PLETHORA of circumstances it could have the advantage.
I can think of some Starmie victories, but they're also shared victories (like "let's all attack together" thing, making it seem even less powerful as an individual)