I was going to suggest the heroes coming out of retirement, similar to above. If they've been retired for a while, though, it might be neat to give the players a little bit of a world-building exercise, having them describe how their heroes achieved fame and what they did with it.
The paladin could have defeated a tyrannical undead creature and then taken over it's lands, making them his kingdom, for example. The wizard could have stymied an extra-planar incursion and then built a fortress around the now closed gate, using its unique energies to aid his researches. That sort of thing.
One thing I've always thought would be cool for something like this would be to have people dust off their old PCs that they haven't played in years and update them to the higher level (and possibly 3rd ed, if needed). Everyone has old favorite characters that they don't get to play any more, and these would come with ready-made personalities and back stories.
As to getting the party together, it could involve divine visions, visitations from powerful entities, threats to dominions or family, etc. All the usual stuff, really. Or you could just tell the PCs what the threat is, and tell them "Ok, you've all been looking into this and have decided to work together to save the world". It really depends on what's best for the players in question.