MM8's replayability problem mainly stems from the fact that the recruitable NPCs never change.
I solved that problem by using a save game editor (MM8CHE, easy to find on the net, if you can't find it email me) to start with five level 1 characters with start game equipment. Just like in MM7 and MM8. And they stay with me the entire game - I forbid myself to use any characters I come across (except Dyson Leyland and Overdune Snapfinger, momentarily, of course)
To make sure the initial stats I give don't "cheat", I create a new game with a template character (so that's, let's say, the trolls I create in the save game editor have corresponding high Might and Endurance values).
Like I said, I use MM8CHE. Here are the steps I use as soon as I create the first character:
1) Immediately save game.
2) Assign Devlin Arcanus, Fredrick Talimere, Simon Templar, and Elsbeth Lamentia to your party (Don't worry, this won't mess up Fredrick's quest, you still get to complete it)
3) Load your game again. Remove all of their equipped stuff into their backpacks (MM8CHE doesn't know how to edit equipped stuff)
4) This step takes long. Create your other 4 characters and save a different game for each one. These will be your templates.
5) This step also takes long. Use MM8CHE. In the original game, cange the aformentioned 4 chars to be identical to your templates, including equipment.
6) Make sure to keep Fredrick's Power stone quest item ( I also like to keep Simon Templar's plate armor, just because)
Additionally, I replace all starting bows with crossbows and all trollish shields with bucklers (the weakest stuff... like in MM7)
I recently just started a game with 5 dark elves this way. Very low starting HP. Great at shooting pirates thanks to bows and high accuracy, but they die as soon as they set foot in the temple.