Assuming the saved searches are truly identical, databases frequently do not guarantee the order of search results unless using explicit ordering. One reason is that in one system, the results may be getting pulled from an index, while in another the same search is doing a table scan because the index does not exist. I have been told by support that when sandboxes are refreshed that all indexes and stored hints are dropped, so that could explain the difference.
tl;dr - Sandbox databases are not identical production. If you want to guarantee the order of results everywhere, you need to order them explicitly.