There are a couple things you are seeing that are by-design, because of performance optimization, but one other thing that we'll log as a bug to fix.
First the "Search as you Type" feature is very expensive, performance-wise, so we have to limit the range that it searches. To have exact duplicates of search results, we'd have to perform the full, expensive (from a performance standpoint) queries with every keystroke, and that's just not workable with nearly half a million members and 4 million+ unique users each month hitting the server farm.
The lack of preservation of results is simply an artifact of the fact that it provides you the answers as you type; it uses a technology called AJAX that in general doesn't allow the preservation of previous pages. It's a tradeoff that for the time being we think is worth it. We want that "search as you type" box to let people very quickly find a recipe. If we had it remember the viewstate, it would be far too slow to be useful.
Another reason you are seeing different results is also a side-effect of something that we think is actually a good design decision. When you do a broad search (not a "search as you type" search), BigOven throws out little words like "on", "a", etc., since exact matches on those words would restrict the search results too much. Try the same example using "Devils Horseback" without the word "on", and you'll see it find the three recipes again in the broader search.
We'll look into ways that we can make these results a little more consistent, but we cannot guarantee anything there -- there are several subtle query optimizations in there to keep the searching rather fast, and we think it's an OK tradeoff if the results are slightly varying.
To do the broadest possible search, use the Find button on the toolbar.