Can't move to an arbitrary search results page outside of cache

When viewing search results, there's a paginaton widget that says, "Page 1 of X". You can change the page number by entering a new value into the text box. However, if you try to change to a page that's not in the prev/next cache, you get a "No Matches Found" error.

I couldn't replicate this on the demo server because there aren't enough contacts - but I successfully replicated this on the master branch. I also can confirm that this bug exists in 4.4.7 and 4.5.6, but does NOT exist in 4.3.3, before CRM-12638 was implemented.