Try it in a JSON array specifying the sort field as well: &sortby=`{"publishedon":"RAND()"}`
It should be working fine. I've just tested your exact call (but with a different template obviously)and it works on my system.
A couple of bluesky ideas:
If you limit the &limit down to say 5 or 10 does it randomly sort? I'm just thinking if there could be timeout somewhere in returning 99 records before they're sorted. You could try turning off processTVs too to reduce the load.
Secondly, are you using MySQL 5.0.51? RAND() is a mySQL function, and there are some issues with ORDER BY queries (not 100% sure what exact effect this c.ould have on RAND() though)