NOLOCK hint changes order of records returned
The appearance of an ordered result set, without an ORDER BY clause, often results from a scan retrieving rows in index order. One reason why an index-order scan is generally chosen under the default READ COMMITTED isolation level is that it reduces the chances of unwanted concurrency anomalies such as encountering the same row multiple times, or entirely skipping some rows. This is detailed in several places, including in this series of articles about isolation levels.

With a NOLOCK table hint, this behavior is relaxed, and access to the table is performed under the more tolerant READ UNCOMMITTED isolation level, which may scan data in allocation order instead of index order. As described in that link, the decision about whether to use an allocation-order or index-order scan is left up to the storage engine. This choice may change between executions without a change in query plan.

This may sound very abstract, but can be more easily demonstrated with some queries using undocumented functions against the AdventureWorks2012 database.

USE AdventureWorks2012;
GO
-- Appears to be ordered by BusinessEntityID
-- File:Page:Slot goes up and down several times
-- Show physical locations with sys.fn_PhysLocFormatter (undocumented)
SELECT
    P.BusinessEntityID,
    [(File:Page:Slot)] =
        sys.fn_PhysLocFormatter(%%physloc%%)
FROM Person.Person AS P;

-- Same query with TABLOCK or NOLOCK
-- Allocation-order (IAM) scan
-- Now appears to be ordered by File:Page:Slot instead of BusinessEntityID
SELECT P.BusinessEntityID,
    [(File:Page:Slot)] =
        sys.fn_PhysLocFormatter(%%physloc%%)
FROM Person.Person AS P WITH (NOLOCK);




The queries are borrowed with slight modification from Paul White.

Finally, just to be clear, this answer is about the appearance of an ordered result set. There is no guaranteed presentation order without a top-level ORDER BY.

An allocation-order scan can occur in a variety of other circumstances, such as when a table-level lock is acquired, or the database is in read-only mode. Parallelism can also influence the order the data is returned in. The key point is that without ORDER BY, the order data is returned in can vary over time by design.