This article by Conor Cunningham (Software Architect, SQL Server Engine at Microsoft) should answer your questions:
Some extracts below:
The hard part here is that there is no reasonable way for any external user to know when a plan will change . The space of all plans is huge and hurts your head to ponder. SQL Server's optimizer will change plans, even for simple queries, if enough of the parameters change. You may get lucky and not have a plan change, or you can just not think about this problem and add an
ORDER BY
.
[...]
There are lots of situations where plans can change in the Optimizer - for more complex queries, there can be thousands of plan choices or more, and each of them has a case when it would likely be picked. For each of those plans, the sort for that plan can be different if you don't specify it.
So, my advice for the day:
If you need order in your query results, put in an
ORDER BY
. It's that simple. Anything else is like riding in a car without a seatbelt.