Should all queries where you expect a specific order, include an ORDER BY clause?
I had a simpler repro in mind:
CREATE TABLE #x(z CHAR(1));
CREATE TABLE #y(z CHAR(1));

INSERT #x SELECT 'O';
INSERT #x SELECT 'R';
INSERT #x SELECT 'D';

INSERT #y SELECT 'E';
INSERT #y SELECT 'R';

SELECT z FROM #x
UNION ALL 
SELECT z FROM #y;

Results:
O
R
D
E
R

Now add an index:
CREATE CLUSTERED INDEX z ON #x(z);

SELECT z FROM #x
UNION ALL 
SELECT z FROM #y;

Results:
D -|
O -|- ordered based on the clustered index, not how originally inserted
R -|
E
R

This still produces the first three rows from #x and the last two rows from #y, so still doesn't prove that SQL Server might return those entire queries in a different order than physically laid out in the query (just that you can't rely on the ordering inside those sets). But clearly this mythical &quot;observe an order once, and it will always be true&quot; statement needs to be nipped.
Bottom line: do not rely on observed order. If you want a certain ordering, say so using ORDER BY.
Also, please read this post by Conor Cunningham, a pretty smart guy on the SQL team.