You have two things working against you:
First is a race condition, where the outcome of your sync operation depends on the timing of Word and that of your sync process. (If you're using something event-driven, the timing is a bit more predictable, but it just means that you're going to delete your history all the time instead of just sometimes as you would if you're polling.) As you observed, there's no way to know how much time will elapse between steps 2 and 3, so waiting to see if the file returns would create another race condition.
Second is uncertainty about whether a file you see as deleted will reappear because the OS can't predict what an application will do in the future. It also can't tell you what application deleted a file, which you might be able to use to draw a reasonable conclusion that the file might reappear.
If Word actually saves files in the way Microsoft describes, that's a flaw in the implementation. Windows has API calls to do atomic renames that would make the process go like this:
- Create temporary file
- Atomically rename
Because step 2 is atomic, your sync program would never see that
Example.doc disappeared, just that its attributes or content changed.
Word's behavior isn't something you can change, so waiting is really your only option.
If the goal is not to lose version history, it's better to make deletions provisional and wait a fairly long time (say, 30 seconds) to make them permanent. This will prevent most -- but not all -- of the problems caused by not knowing how long a save takes. Obviously, it's possible for a save to take that long, but it's probably rare. The bigger pitfall is that a long enough provisional period will treat a delete/create sequence done by a human in that time as a version change rather than what it actually was. This doesn't reflect the reality of what happened, but it will preserve the version history.
The question only you can answer is whether having reality distorted like that on relatively rare occasions is acceptable in the face on not having your synchronizer blow away the history.