Minor point... At the end of the article where you say you could set the uniqueID column as a pkey I think you mean to set it as a clustered index thus allowing returning of rows in the GUID order without any sorting effort.  Common to mix up the pkeys & the clustered index of a table as they often tend to be one and the same if the defaults are accepted

It is tricky getting random data in a set-based fashion.  Perhaps you could do something along the lines of

1. Having a unique row number for each row in your table without gaps - an identity column would be perfect

2. Indexing by this column either clustered or using at least a covering index

3. Use some mechanism to generate row numbers to select. Perhaps the pairs of digits in a generated GUID (or triplets, quads, etc depending on how many rows you have)....

Step #3 might be the lengthy & wasteful bit though.....  Will give it some more thought