1. Если неприменно нужно от текущей даты, то вот пример из BOL

"SELECT RAND( (DATEPART(mm, GETDATE()) * 100000 )+ (DATEPART(ss, GETDATE()) * 1000 )+ DATEPART(ms, GETDATE()) )

When you use an algorithm based on GETDATE to generate seed values, RAND can still generate duplicate values if the calls to RAND are made within the interval of the smallest datepart used in the algorithm. This is especially likely if the calls to RAND are included in a single batch. Multiple calls to RAND in a single batch can be executed within the same millisecond, which is the smallest increment of DATEPART. In this case, incorporate a value based on something other than time to generate the seed values."

2. А мне больше по душе такой способ

select a.* from mytable a
inner join(select top 1 newid() as random_id, id from mytable order by random_id) as b
on b.id = a.id

2alexeyvg
Проверил каждый вариант 3 раза по 100 (в цикле) на таблице из 123000 записей на 2-х разных серверах(оба SQL2000 SP1, Win2000 AdvServer SP2): без индексов, с кластерным индексом, с некластерным индексом. И во всех случаях не увидел ни того, что newid() выдает значения попорядку(или что вы имели ввиду под "последовательные номера random_id"), ни того, что наличие/отсутствие любого индекса влияло на результаты запроса, хотя в плане выполнения запроса присутствовал объект Index Scan.

Не думаю, что аппаратура, ОС и окружение должны как-то влиять на работу функции newid().

PS.
А что означает "и order by соответственно всегда по кластерному индексу" ?

Что вам мешает вычислить номер записи один раз по расписанию в 00:00:01, записать его в таблицу и в дальнейшем использовать уже готовое значение ?