I'm not sure I understand the issue here, but
they don't actually have to be totally randomized. You could use a
PRF so they were predictable to the CA.
That works. This works too: the serial number could be composed of
two parts, where the most significant bits are a counter and the
least significant bits are randomly generated.
Russ