make prerequisite is newer than target but target is not ramade

Question

I have a problem which occurs from time to time (not consistent) during compilation of our project: Part of the compilation creates "archive" (.a) files. For some reason, one of these archives is missing an object, which later on leads to failure in the final linkage. Here is the code in the makefile which does this:

$(MODULE_LIB): $(addprefix $(OBJDIR)/, $(COMPILED_OBJECTS) $(EXTRA_OBJECTS) )
    @echo 
    @echo Insert files into target archive = $(MODULE_LIB)
    @rm -rf $*.tmp.a ; mv -f $@ $*.tmp.a 2>/dev/null || true
    $(AR) -s -r $*.tmp.a $?
    @mv -f $*.tmp.a $@
    chmod uga+r $@

MODULE_LIB is "libEXC.a"

The object file ($(OBJDIR)/$(COMPILED_OBJECTS) is "EXC_DesignDependent.o"

I've added the "-d" flag to our make procedure and here is a snippet from the last lines:

    Successfully remade target file `/WARTS/wrkdir/1481986500184/EXC/objs/EXC_DesignDependent.o'.
    Finished prerequisites of target file `/WARTS/wrkdir/1481986500184/static/libEXC.a'.
    Prerequisite `/WARTS/wrkdir/1481986500184/EXC/objs/EXC_DesignDependent.o' is newer than target `/WARTS/wrkdir/1481986500184/static/libEXC.a'.
    No need to remake target `/WARTS/wrkdir/1481986500184/static/libEXC.a'.
    Finished prerequisites of target file `EXC'.
    Must remake target `EXC'.
    Successfully remade target file `EXC'.
    Finished prerequisites of target file `ROOT'.

As far as I understand this, the object "EXC_DesignDepedent.o" should have been placed into the archive "libEXC.a" since it is a prerequisite to it and "make" clearly says its newer then the target.

I've made sure we do not have any "|" in the prerequisite which might have declared a prerequisite as an order-only type and not "normal" type.

In order to validate that the object is indeed not part of the archive, I ran the following command:

nm libEXC.a | grep ":"

and I got this:

EXC_MainLoop.o:
EXC_Generate.o:

Now, here is the most tricky part of all: This code runs on 5 different environments. It completes compilation and linkage flawlessly on all of them. Only in one of those environments, it fails with the above failure from time to time (about 1% of the times). The failure is always the same, but its not reproducible (completely sporadic - we tested different machines with the same environment with the exact scenario. The fail is completely random in its occurrence as far as we can explain it). I've been racking my brain at this for several weeks now, and would appreciate any idea which might point us in the right direction.