I the found the link below when I was researching how to get a random record for a database. This article is about speed in retrieving a random record and I found in my test that speediest solution brought about the most duplicates.
http://akinas.com/pages/en/blog/mysql_random_row/
I am hoping some one has a solution that they have tested that they found acceptable.