This has been discussed twice on WebmasterWorld:
There certainly isn't a consensus in those threads. Here are some excerpts from the comments that I find most compelling:
Tedster:
In a word - yes. Random links have often created ranking troubles, especially if the links are newly generated with each page load. Especially at launch, when you have so many challenges to deal with just to begin to establish visibility and trust, I would not suggest doing this.
Sgt_Kickaxe:
Problem: the pages are fairly dynamic though they do draw descriptive information via rss from sections of my own site. Being that they are dynamic I couldn't easily assign a permanent link to each page and so the links are random, but relevant. I only have 100 or so random links in total and show 5 at a time.
So far so good, Google doesn't seem to be penalizing the site at all. It may take 3-6 months before I can know for sure but after 2 months all is well.
Walkman:
No, I do this on a site and it got increased traffic. So by itself they don't harm you
Robert Charlton:
That said... and playing devils advocate here... I've occasionally seen relatively large sites with randomly rotating product menus for their less important related products, which overall appear to do surprising well, well enough in fact that I've wondered whether they know something that I don't.
1script:
I actually have a number of forum sites using a somewhat similar feature - Related posts. I would not call the links random of course because the degree of similarity differs and some post are really more related, so only those are shown. But those links aren't static either because with new discussions the list of related posts always updates.
I've never tracked any effects on ranking except for maybe one obvious one: you can't rank for anything at all if Googlebot hasn't seen the page, and I hope that those links help Gbot learn about more URLs on my site. Getting them to index more pages has always been an uphill battle for me, so I've kept these links just for indexing sake.
