This thread is NOT a "please help me" thread, let's be very clear about it :)
Simply, I am
(1) reporting a problem, just in case, and
(2) providing the workaround to this problem, if other webmasters are confronted to the same situation :)
So, having a good number of reports, over time, that the Random Redirect plugin didn't work on my blog, only loading the homepage instead, I finally created a poll about it.
And the results were crushing : over 700 votes in one day, 60% of the voters telling it didn't work :(
(I'm sorry I can't give the URL to my blog and to the poll, it's a private place)
It may be related to the Wp Supercache plugin, but I doubt it, its admin, Donncha, has cleared the plugins mutual incompatibility a long time ago (cf this page)
One solution has been given by a visitor in the comments : adding a = character in the end. Meaning having an url such as domain.com/?random=
I don't know why this plugin doesn't work for 60% of my visitors, and I don't know why adding an = character in the end fixes it.
But it works, maybe the info will be of help to some people :)