Kingdra has 1 solid counter, actually, called Empoleon. Reists dual-STABs and doesn't give a crap about Hidden Powers.
Roserade is harder to stop simply because it beats all the spinners in UU (Blastoise, Hitmontop, Claydol, Kabutops) excluding Delibird but that's Delibird. It's also got massive offensive presence and can effectively run Scarf or Specs. Still, got counters like Bronzong.
I think Raikou is the closest comparison to Mew, to be honest. Raikou can run HP Grass to beat out Rhyperior and Swampert, which leaves it vulnerable to Gligar I guess, and Aura Sphere to smash Snorlax to a bloody pulp. It also gets Weather Ball from the Aura Sphere event and it's devastating in Hail. It's also horribly vulnerable to 4mss, which is, I think, a major problem with Mew.
With Mew, you're either going to be running NP/SD+3 attacks or 2 attacks w/ recovery. With 3 attacks your choices are pretty much unlimited, but then you have to rely on that natural bulk to do anything, especially if you run a resist berry as suggested (gimmicky) to beat certain Pokemon. With Recover/Softboiled in the last slot, however, you can't get perfect coverage and you pretty much can't run your STAB attack because of coverage issues. Psychic/Dark? Other Dark-types, which beat you anyway. Psychic-Fighting? Say hello to other Psychics. Psychic/Ghost? Meloetta, who can effortlessly set up CM on you regardless of what you do, because it can KO you faster than your Psyshock can dent it. So you're essentially forced to run Ghost/Fighting, which is decent (but no SE coverage on SABLEYE) or Dark/Fighting which is essentially the same thing but misses Heracross. Huge problem there.
The way I see it, you can either set up an boost and sweep with Lefties, running the risk of being revenged and forced out, or running LO or a resist berry and just not giving a crap when the supposed counter comes in. You honestly compromise too much bulk to be effective with a resist berry, imo.