I was in a similar situation to you a little over a year ago, although from the sound of it our situation was a bit more dire:
I learned that there were a number of patents (12+) that covered nearly every variation of our business method EXACTLY, and all were held by just two large companies. They were also the only two companies I could find that were using these business methods, and I couldn't find any pre-existing art. I was ready to slit my wrists. [One of the two companies has an IP division that will license the patents for royalties, but the other company wouldn't even talk to us except to threaten us.]
I spent a few weeks reading the competitive patents, and then found a 'loophole' than not only enabled us to compete with them, but that allowed us to generate several new revenue streams and to strengthen the strategic position of another one of our portfolio companies. The companies with the competitive patents had also been successful enough (Billion$) that they essentially proved our business model, so signing up partners is becoming easier for us. The fact that our competitors had great patents actually ended up helping us in the end.
In our case, the initial breakthrough for finding the 'loophole' was realizing that by focusing on an alternate "concrete and tangible result" to the competitive patents, we gained an entirely new perspective. Say, for example, that the competitive patent's "tangible result" was financial savings for retail investors. Our "tangible result" might then become generating new business for a brokerage firm, not saving money for the retail investors. That little change in perspective might suggest a different business method, perhaps even one that is better. I'd give our specific example, which would be much more clear...but that would be giving away the store a bit. We're still in the process of patenting OUR new business methods, so that we can cause some other startup intense psychological pain ;-)