The AVR processor is perfectly deterministic with only two exceptions: the amount of time needed to write to Flash; the amount of time needed to write to EEPROM. Even those may be deterministic. The datasheet is vague on the matter and, to the best of my knowledge, no one has bothered to run the test.
PoisonNuke:
And if I exchange the UNO boards (exactly same revision) and run exact the same code and get different results, what is going on?
Corrupt heap, race condition(s), uninitialized variables.