Is there a moment where a file "doesn't exist" during a rename?
The actual guarantee in POSIX is that if you rename a to b and b already exists, there will be no point in time during the rename when b does not exist. It will refer either to the previously existing b or the new b formerly called a.
If b does not already exist (which appears to be the case in your example), then the guarantee doesn't apply. It is possible that there's a moment when neither a nor b exists (it depends on how the particular filesystem works). It's also possible that there's a moment when both a and b exist (and refer to the same file).
Your proposed solution of checking twice with a short delay is probably the simplest approach.