Why does xelatex produce different files from the same deterministic sources?

The issue is related to the driver: xdvipdfmx. In order to generate unique tags for fonts, random number is used. Try

xelatex -no-pdf test

xdvipdfmx test.xdv
pdffonts test.pdf

The tag will change like

LYKESP+CMR10
CBIVMK+CMR10
...

each time you run

xdvipdfmx test.xdv

What seems to differ is the actual binary encodings of some parts. I trust that the pdf rendering does not vary at all. In my experience the file size changed only by plus or minus 1 byte (mac os x). I have done an ediff in hexadecimal mode of two such pdf's, here is a snapshot of where the first differences appear:

This first difference thus occurs in a part of the pdf relative to the partially embedded font. I don't know what causes this.

Generally speaking I can imagine that if you have say some 213 bytes thing which must be stored in 256 bytes, then the last 43 bytes may be random memory, if moreover one or many such things together are compressed then you get varying result. On undecompressing, there will be some varying random junk after structures terminators (or after a given number of bytes). Like non-coding DNA. Which perhaps is not so much non-coding, but let's not digress.

Only someone familiar with XeTeX source code can answer convincingly I guess.

Don't worry about the C-M-' undefined, I was trying to capture the thing via keyboard shortcuts I had forgotten.