i guess a good way to tell what pokemon are generally better would be to look at the 4 Pokemon currently in Top Tier: Drilbur, Darumaka, Magnemite and Scraggy. Drilbur and Darumaka possess a good combo of offense and speed, Magnemite and Scraggy have extremely good typing to complement their lack of speed (the former gives it a lot of resists, the latter is a generally good typing for both offense and defense), and in Scraggy's case, a good boosting move and ability for sweeping (Bulk Up, Moxie). All four have powerful moves early on to spam with (L33 Flare Blitz for Darumaka, L36 Earthquake for Drilbur, Thunder TM for Mag and L31 HJK for Scraggy). They also come noticeably early: the earliest you can get Mag is before Roxie, and the other three before Burgh.
star's issue is that it comes pretty late, however it's still one of the best in-game fillers because you can get appropriate moves for STAB almost immediately (Surf, Psychic) then fill up the rest of its moveset with good coverage moves (Thunder, Blizzard). not mentioning its immediate utility against Drayden and Marlon due to Boltbeam coverage. It even helps destroys Garbodors and other poison types in the Frigate. Starmie's E4 performance is sadly mediocre, but its useful against Iris due to Ice Beam. I think it should probably be high tier.
@layell: i think the only time when you need to recatch a pokemon is Azurill because the ability makes a very large difference in its usefulness...