I have also not had time to benchmark performance, but here is another technique that gives the illusion of randomisation:

ORDER

BY SUBSTRING(REVERSE(REPLACE(table.textcolumn,' ','')),convert(int,rand()*10),1) ASC

This uses the text in a column from the query, reverses it and removes spaces, and then extracts a randomly selected character to order the results.

Obviously this is limited to situations where you have a text column to work with...