This question is similar to Overcoming Fear of Rejection, but not the same.
My experience in academia was teaching Computer Science for four years at a mostly liberal arts college, and that was 30 years ago. I frankly found the world of work to provide more challenging intellectual stimulation, at least in the sort of practical issues I cared most about.
There are highly technical issues in software development that I and other practitioners have discovered that are quite orthogonal (to say the least) to the trend of publishing in those areas. So when I try to publish it is hard to build much of a bibliography. When I submit (through an online submittal process) I tend to get responses that vary in quality, but are generally negative.
I am tempted to revise, in such a way as to address the concerns raised by the better quality reviews. I could buttress the claims with stronger mathematical arguments, but it's hard to tell if this would make the paper more or less approachable.
Then there's the question whether I should resubmit to the same journal. There don't really seem to be any others at the same level of relevance to practitioners.
Sorry if this is a noobie question.
I certainly can't speak for all reviewers, and what I'm saying might be true only for me, but when I review a paper, I try to ask myself three questions: is it interesting for the venue? is it correct? is it improving the state-of-the-art? I need to be convinced that all answers are "yes", and the burden of convincing me is on the authors.
A problem I've seen with some papers is that they focus mostly on showing the correctness of their approach, and at first glance, it seems to be the case with the paper you're describing. Showing the interest of the approach is tricky, because often the authors are convinced it's interesting (otherwise, they probably wouldn't work on it), and they to think that everybody else understand why it's interesting. Similarly, explaining why it's improving the state-of-the-art might be tricky, especially for novel approaches, but it's necessary to explain why other approaches won't work. You have the right to write: "To the best of our knowledge, this approach has never been used to tackle this particular issue", but then, as a reviewer, I need to be convinced that your knowledge is good enough to make this kind of claim.
Basically, in your situation, what you need is a compelling example (e.g., a situation/use-case where your approach is either the only viable one, or where you can show with experiments or formal proofs that yours is better than others). If you can focus on that point, then you can probably resubmit it to the same journal, but it's possible that you will get some of the same reviewers you had the first time.
Another solution could be to publish the paper first as a technical report (e.g., on arXiv), try to submit it a short version without the proofs and technical details to a specialised workshop, where maybe you can get interesting feedback from the community (for instance, some recent related work), and then use that feedback to improve the paper.