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.