Starmie can Hydro Pump Azelf down to its Focus Sash and then hope that it wins the speed tie to finish Azelf off with Rapid Spin and get rid of Stealth Rock at the same time. If Azelf is a dual screener, Starmie needs to hope that it wins the speed tie and Hydro Pump before Azelf Light Screens.
A smart Aerodactyl user will Rock Slide first turn, hoping to get the flinch and allowing the 2HKO on Starmie before Starmie can spin away Stealth Rock. For this reason, it is best to switch to Metagross immediately. Metagross resists Rock Slide and can then Meteor Mash and Bullet Punch, while Starmie can Rapid Spin away Stealth Rock later. If Aerodactyl Stealth Rocks on the switch, it will usually Taunt Metagross to prevent Stealth Rock from being put up, allowing Metagross to KO with Meteor Mash and Bullet Punch anyway. Metagross is also able to survive Aerodactyl's Earthquake.
Starmie matches up well with Swampert, 2HKOing Swampert with Hydro Pump, meaning that Swampert has to choose between doing damage to Starmie or using Stealth Rock, which can be spun away later.
Starmie handles Metagross the same way it handles Swampert: by forcing it to choose between doing damage and getting up Stealth Rock before being KOed. It is worth noting that not even a Earthquake + Bullet Punch + two turns of Life Orb damage will beat Starmie, allowing it to come back in and spin later.
Fearing a Choice Scarfed U-turn, I find it best to switch immediately to Metagross, who has the bulk to take just about any attack from Jirachi. Meanwhile, you can Earthquake Jirachi for major damage or get Stealth Rock up.
Starmie matches up much better with Infernape than Metagross, being able to Hydro Pump Infernape down to its Focus Sash and then Rapid Spin away the Stealth Rock.
Machamp will use Payback, so it is best to switch straight to Metagross, as Payback and DynamicPunch will not beat Metagross. Metagross can take a DynamicPunch while its Lum Berry cures it of its confusion, allowing Meteor Mash to 2HKO Machamp, which thanks to No Guard, will never miss.
Lead Roserade usually Leaf Storm a lead Starmie, so it is best to switch to Metagross, who resists the Grass-type attacks. Metagross can then beat Roserade with Meteor Mash + Bullet Punch, while Lum Berry renders Sleep Powder useless.
This is one time you will wish you led with Metagross instead. A risky match-up, since if Starmie switches out while Tyranitar Pursuits, Starmie is dead for nothing. I find that Starmie is usually too important to sacrifice for a little damage and that lead Tyranitar with Pursuit are rare enough, so I often switch out to Metagross, which beats Tyranitar quite nicely with a super effective Meteor Mash.
Starmie is a very deadly opposing lead for Gliscor, as it can hit all switch-ins hard if the Gliscor user mispredicts. I find it best to Hydro Pump first, as that does the most damage in case a Tyranitar or Scizor is switched in. Another lead that Starmie fares better against than Metagross.
Starmie frightens Heatran, as it can OHKO Heatran with Hydro Pump. Again, Starmie fares better against Heatran than Metagross does.