"I'm not sure what you mean. Isn't that exactly what it says it should be doing on MSDN? Can you rephrase that?"

I missed the word 'not'.

Microsoft specify that sleep() will suspend the thread for AT LEAST the requested number of milliseconds. The problem appears to be that it occasionally suspends the thread for LESS THAN the specified number of milliseconds, which is contrary to the published behaviour.

"So Sleep() is only a message that you send to the OS."

No it isn't, it is a function call which immediately suspends execution of the calling thread.

"The OS is an asynchronous, time discrete system and you are sending a message to it at an arbitrary moment with a request for a delay near its granularity."

What 'granularity' are you talking about? Do you have any idea how the preemptive scheduler measures time slices?

"Should one expect large percentual errors, or should one sit back and think: "I think it'll work just fine, and if it doesn't, let's blame Windows"?"

No, one should read the documentation and expect the implementation to behave as described. If it doesn't, you blame the documentation or the implementation - either way it's Microsoft in this case.