Precisely because without putting a protein that is structurally similar to ubiquitin in the first genomes, you'd have to depend on the blind watchmaker to tinker around with the existing folds, and "just happen" to come up with a protein that is structurally similar to ubiquitin (and also happens to have the necessary sulfur chemistry).
What makes you think either the sulphur chemistry or the protein fold is necessary?
Ubiquitin is a signalling molecule that interact with other proteins. I'm not aware of any reason to think that it isn't arbitrary which features of Ubiquitin are required for it to function; all it needs is the correct "lock and key" interaction with the various other proteins it interacts with.
The universal distribution of ubiquitin among eukaryotes strongly implies that it is necessary for eukaryotic existence, does it not?
It implies that our Eukaryotes require it, yes, but it doesn't imply that life like a Eukaryote requires it. There's no reason to think that we couldn't engineer a Eukaryote so that it used a different molecule in place of ubiquitin, it'd just need every protein that interacts with it to be re-worked - which is why evolution can't do it.
Ubiquitin is a signalling molecule, not an enzyme, it's functionality lies in its interaction with other proteins, not it anything inherent to its structure (well, it needs to be small, easily synthesized and capable of being combined into chains but that leaves literally thousands of possibilities).