Order By In A INSERT INTO..SELECT

I have the following basic statements being executed:

Create a temp table, #TempPaging

Insert Into #TempPaging (Col1, Col2)
Select Col1, Col2 From SomeOtherTable Order By Col2, Col1

Select * from #TempPaging

I can't provide a reproduceable scenario right now without making this
into a 200K post, so I'm hoping someone will know what the issue is.. I
can't find anything regarding this in BOL.

Basically the order is off a little bit every now and then when there
are large amounts of data, like more than a couple hundred rows. Is
there something I need to do to guarantee the originally selected
order?

This is very important that it be in order from the original select
statement as this is for paging. Adding an order by in the second
select from the temp table will not fix the problem. In this particular
instance that I have reproduced we are using SQL 2005 but have also
seen this on SQL 2000 servers. I had previously asked this question as
I was using a SELECT INTO statement, but now we are manually creating
the temp table (Pain in the ass) and still having the same issue. Best
case scenario is for it to work for a SELECT INTO.

Any ideas?