Rescue Mission: An NPC could be held hostage by a group of bandit pokemon for the player to rescue. Once rescued (by defeating the bandits of course), the NPC would temporarily join the party and be taken back to town to finish the quest. If the NPC faints, it'll re-spawn back at the location it was found.

Stranded Pokemon: Like above, but without bandits guarding it and the NPC is just stranded deep in a maze or whatever.

NPCs being rescued should be maybe 10-15 levels weaker then the players, and they should probably have very weak moves as well, and be programmed to run away from enemies in combat. On the map they don't appear ( couldn't imagine how many encounters they'd cause that way), just a little icon that show's they're in your party perhaps, and appear only in combat. Keeping them safe until you reach town would maybe be quite a challenge, but at least that's better then Kill X Pokemon quests.

Following the idea of allowing NPC allies in fights, what if we could recruit mercenary pokemon NPCs? Their typing would be in favor of the area they're in, and they'd be beneficial to players who can't get a hold of good team members. They'd just be very costly to keep, an amount of pokedollars appropriate to the area they're in, like for example $15 per battle in the beginning area, $200 dollars per battle for Pinchin' Sands, etc. The pricing could also vary by your level and/or your other teammates levels, lower if yours is higher and higher if your is lower. When you no longer have sufficient funds, the merc leaves your party. Obviously it should also leave your party if you log out or just give a option to let it leave your party when you no longer need it's services.

The merc idea might not be a great idea, since this is a multiplayer oriented game, but I thought I'd just toss that idea out.

Would be nice, but that would be a fairly big overhaul to add or change quests in every area coded so far. The mercs sound nice too but it is indeed a multiplayer oriented game. To build on that fact, I should think players wouldnt receive the party bonus experience for mercs either if they were in at all.

Perhaps, but really anything different from Kill X Amount of Pokemon quests would be a lot more enjoyable. 

Yeah, if a merc feature was added, it'd make sense to not get a EXP Bonus from them. There should probably also be a limit of 1 merc per party, as to not let players just save up enough money to play with a full party of mercs.