Ugh, yes, the practice of short-lived machines throws off the assumption of "when it was last shut down." You are totally right that this is a concern.
The ideal solution to this would be for hypervisors to just pass a random seed to their guests. (There is even a full virtio-rng device in qemu, it just seems to have /dev/random semantics from a quick glance.) I don't know how we get to the point of convincing the big cloud providers to start doing this, though.
