Ah, yes, I see what you're saying. That's always going to be true -- rand() can't possibly guess.
You have a few options:
1) Just increase the number of rows you return randomly, if you can easily the "miss rate". This works well if you don't need "exactly" N rows back.
2) Do (1) iteratively, since maybe you will get back the right number sometimes -- can't imagine that a few extra passes wouldn't sort this out.
3) This may be very bad performance-wise, but if your "expired" query runs quickly, you can always use those UIDs directly -- but that's quite ugly.