I agree that the lack of a clear "no pages matched your query" is large part of the problem. And as your phrasing indicates, it's also worth distinguishing between "not in their index" and "doesn't exist on the web". Google has a very large corpus, but doesn't include everything.

But the odd part here (and in line with original post) is that there are pages in Google's index that include both terms: https://discussions.apple.com/thread/7169461?start=0&tstart=.... It's just that they don't start until 40 or so results in.

Searching in Verbatim mode without other modifiers seems to create the response that the original post wants: https://www.google.com/search?q=deluge.app+retina&tbs=li:1