That would be really cool if there was also a procedural world generation so every experience is slightly different. Pokemon aren't in the same place for everyone, checklists might be different, certain Pokemon might be a little different, etc. I'm thinking of a cross of roguelike elements with Pokemon: like expanding the premise of the Pokemon Mystery Dungeon games.
Well, if you really wanted every experience to be different, you could use my absolute favorite algorithm ever. When the game starts you seed the environment with Pokemon, and have a loop running in the background which periodically makes a huge amount of quick battles happen, and then those (non-user) pokemon which beat other (non-user) pokemon get an appropriately large amount of the space they inhabit. In this way, you would actually see an automatic progression to more powerful pokemon, real evolution, and make it impossible for anyone to spoil the location or types for anyone else. I love the Genetic Algorithm so freaking much.
There could be all sorts of neat ways to implement the procedural content. While it might be harder with a GA, I was thinking that it might be neat to be able to share the seed. That way that people could, if they wanted to, play the same instance and share secrets for that instance. Kind of like the "password" system in the fictional .hack where 3 words seed the content so you can share the same zone between players and the WonderMail system in Pokemon Mystery Dungeon.
Great idea! Having a user-accessible seed for a GA seems like a great way to create a potentially "unique" but sharable experience! Man, I needa get this 2d physics engine finished.