I don't have all the details, but I think the conditions are not easy to identify. I am aware of several categories of challenges:
Many instructions may have undefined behavior (e.g., the opcodes are reserved, or the spec does not define their behavior for some inputs), and thus it is possible that their behavior might vary on different CPU models. For instance, many instructions specify that some aspects of their effects are undefined, e.g., the effect on some flag bits may be undefined. As another example, SHLD says that the contents of the destination operand is undefined in certain cases.
There are certain instructions that explicitly perform I/O or read external data: e.g., IN, OUT, RDTSC, RDTSCP, RDRAND, RDSEED, etc.
Concurrency can cause nondeterminism, so you would have to rule out all associated instructions (e.g., LOCK). Also I think there is a lot of nondeterminism in the memory model when there is any concurrency or shared memory. So, you have to ensure that no other process/thread/etc. has access to any shared memory. You'll also need to make sure that the program does not make a system call to the OS to initiate DMA.
System calls or interrupts (e.g., the INT, SYSCALL, SYSENTER instructions) might not have deterministic behavior.
I'm not sure, but I suspect reading machine state might have nondeterministic behavior, e.g., reading the machine status word, global descriptors, reading timers and performance counters (e.g., RDPMC), CPUID, model-specific registers (RDMSR), etc.
Supervisor-level / kernel-mode instructions are complex to analyze and I don't know whether they will be deterministic. If you want to ensure determinism I would suggest you ensure the code runs in user mode (e.g., ring 3). For instance, I don't want to think about instructions like VMLOAD, VMRUN, modifications to the page tables, etc.
The initial state of memory before it is written to is not defined and thus any program that reads from uninitialized memory may trigger nondeterministic behavior. On the other hand, many operating systems zero out pages before handing them to the program, which eliminates this issue.
This is a complex topic and I wouldn't be surprised in the least to discover that I have missed other important challenges.
I don't know whether floating-point arithmetic is guaranteed to be deterministic and bit-for-bit identical on all platforms.
I think it is plausible that, given enough effort, you could come up with a subset of x86 instructions and an initial state for the process where, if the process only executes those instructions, its behavior will be deterministic. However, coming up with this subset might be quite tricky and require a lot of time with the Intel manual. Enforcing that the process only executes instructions from this subset will be quite challenging, given the ability to execute self-modifying code and runtime-generated code. It is also not clear how you will deal with instructions where some of their results are undefined. For instance, it's not clear how you'll deal with instructions that leave some of the flags undefined (and there are many of them), as there is a risk that a later instruction reads one of those flags whose value is undefined, and this could introduce nondeterminism (the spec makes no promises that undefined values will be a deterministic function of the inputs you care about). So, I suspect ensuring determinism at the x86 level would be a non-trivial project.
If it is helpful, I know of some efforts to enforce determinism in the context of higher-level programming languages, where the enforcement becomes easier; you could ask a separate question about that, if it is of interest.
