I don't know . . I use it, it's never been a problem . . . but I suppose they are right. :-)
If you have an ID field in the database you could first get a random number
The only problem with that is, what if a deleted record's random number is selected?
select count(*) from rows, pick a random number in between 1 and $count, then
... order by whatever limit $count, 1
Even if "$count" has been deleted, it will pull the next record starting at index $count.
create a second table with a single int() column, populate it with existing record handle id's. As new records are added (and deleted, remove them), drop the id into this table. Do your rand on that, then select the result