I submitted a paper in math/cs/economics to a top-level journal. The paper involves a new variant of a well-known problem. All reviewers agreed that the results are interesting and non-trivial, but they rejected the paper as not being general enough for their journal.
Encouraged by the positive feedback, I submitted an improved version of the paper to a medium-level conference. The improvements include simplifications of some of the proofs and additions of stronger results about the same problem. Now the reviewers rejected the paper claiming that the results are too weak and unsurprising!
What should I do in the next time I submit (to a different journal), in order to make the reviewers believe that the results are indeed surprising and non-trivial? I don't want to write the proofs in their more complicated version, as in the first revision, because this is unscientific. But writing it in a simple way seems that doing so creates a false impression that the results are too simple. What do you suggest?