i think that instead of a starter you have to go and catch it from a small field full of pigeys, starlys, hoot-hoots, ratatas, bug pokemon, etc. But after you get a little into the game, each trainer should be able to talk to someone who gives them one of the 12 starters plus a few other pretty decent pokemon. So theres like a total of 20 pokemon that you can get from this guy.
i also say that their should be VERY strict rules for being a gym leader. you should have to clock atleast 10 hours online a week, unless you post something on the gym door and find a sub to handle the battles for a week or two if your on vacation or something. i also think that an extremely powerful gym leader shouldnt be allowed to create a gym full of super powerful monsters right by where you start the game. (which could be either starting point from the original 4 games) The game should regulate how strong a gym leaders pokemon can be in certain areas too.
Or maybe even level the trainers, so before agreeing to battle that certain trainer, you get to see their badges, win loss record, and hours played, etc. that would keep newer trainers from getting owned and veterans from being jerks to newer trainers.
In terms of battling, i think they should use the same system that they have gone with, but use a little more stuff from the show (i know the show isnt that great, but the battles are well made)
well, im sure i could go on, i think ill stop there. A pokemon mmo is a great idea btw!