I think Paul is the first to get this right: it is almost certainly due to NOLOCK allowing an allocation-order scan. if you want the same rows back on a top repeatably you MUST include an order by that guarantees uniqueness of the returned rows. Otherwise SQL Server can return ANY rows - there is NO 'ordering' in set-based returns other than that given by explicit ORDER BY.

To address a comment someone else made "Using With(Nolock) can improve performance . . .": actually it doesn't technically improve performance as such (other than the tiny fraction gained from not taking/checking some locks). What it really does is improve CONCURRENCY, meaning your read isn't blocked by other DML activity. 🙂