I think the Create Random Points tool does just that: creates new points randomly, rather than selecting existing points randomly.
You could try adding a new field to your existing points, then calculating a random 1 or 0 for each point, then just select out the 1s. I think it could still be a bit random how many 1s you get though, it might not reduce the points by much.
If there was a certain factor you wanted to reduce the data by, and as long as the OBJECT_IDs aren't sorted in any way, you could calculate a modulo in your field, e.g. to just pick out every 10th point, you'd calculate OBJECT_ID % 10 (which would give you the remainder left if you divided the OBJECT_ID by 10) and select all the 0s in that field.
Hope that makes sense, if not let me know and I will try to explain better!
Dan