The patent doesn't expire for quite a few years from now.
One of the big differences between my application and the existing one, is that the existing patent has such a general scope as to how it would work that it could not conceivably create a reliable result.
As a comparison point, I'd say their patent is like somebody patenting 'a system for the search and retrieval of webpages where results are ordered by relevance' where my application is much more like google pagerank, which describes the method for calculating and creating the relevance order. Note: neither patent is related to web search.
Any suggestions on how to handle a situation like this? I figured there would be prior art, but hadn't been able to track any down until now.