I have had similar experiences to the OP and I think the OP is handling it correctly. If I'm rejecting a paper which is (apparently) correct and new on the basis of an opinion that the result is not good enough for journal X and I get it again from journal Y of a similar quality as X, then clearly I have a different opinion from the author about the paper's quality and I think the author deserves a second opinion.