A simple idea (not simple to implement of course).
Create a randomized adventure where no guides can be used to run it. There should be multiple levels of difficulty. So a player can choose if he/she wants to do an simple, easy, medium, hard or difficult adventure. You could use the same maps you have now, but move the camps around and adjust the troops in the camps.
Some control is needed as far as making sure that the game is not creating camps that cannot be beaten. I think this would be a welcome change for many players. Of course some would not like it and that is okay. How many players are enjoying PvP ? I don't know the answer, but I know there are many that completely avoid it.
If you do create random adventures that players have to figure out how to win each time, please make sure the rewards are worth it. There is no sense building something that players will not like and therefore will avoid.