I know that normally traded Pokémon won't obey you over certain levels until you have the right badge. I have never heard of Pokémon you caught naturally not obeying you because you don't have the right badges (there are some crazy, crazy people out there who train their starters against level 4 wild Pokémon to level 50 or something before the first badge, and I've never heard of them having problems), and I've never heard of hacked Pokémon not obeying you, because in most cases I don't think there's a way for the game to be able to tell that the Pokémon is hacked.
However, at least in Gen III, some event-only Pokémon were made so that they wouldn't obey you until you had all the badges, like Mew. This would prevent people from hacking a Mew early on and using it for the whole game. Perhaps Gen IV has the same settings on some of its event Pokémon.
That's all I can guess, though. I don't know why you'd have that problem with starters.