Any clever ideas on how to find some random records?

I have a MySQL database with about a million records. I'd like to use the SQL command "order by RAND()" but my ISP won't let me: whenever the server gets spidered, Google overloads their MySQL server because of all the overhead of that command. I can't just cloak the spiders because I need them to find the random pages. So...what I've been doing for small sets of records is to use PHP to generate a bunch of random record ID's, then I construct a long SQL statement to find all the matching records. This works, but if I want to generate a big index page to list a hundred or a thousand records, it could get pretty clunky. Anyone have any better suggestions? :)