Following your code check I did the following after setting mxd to the current map document...
>>> for lyr in arcpy.mapping.ListLayers(mxd, "*Replace*"):
... print lyr.dataSource
...
C:\***\*****\F_Geodatabase\*****.gdb\ReplacementTree
>>> for lyr in arcpy.mapping.ListLayers(mxd, "*Replace*"):
... print lyr.dataSource
... print arcpy.Exists(lyr)
...
C:\***\*****\F_Geodatabase\*****.gdb\ReplacementTree
False
>>>
The layers are being re-sourced via another arcpy script already. Trying to manually change it in the layer properties results in the same output. In order to get it to work, I need to actually hit the add data button to put the data into the TOC. That results in:
>>> for lyr in arcpy.mapping.ListLayers(mxd, "*Replace*"):
... print lyr.dataSource
... print arcpy.Exists(lyr)
...
C:\***\*****\F_Geodatabase\*****.gdb\ReplacementTree
False
C:\***\*****\F_Geodatabase\*****.gdb\ReplacementTree <--Put in here by hitting add data button (same file)
True
>>>
The script that fails has a pre-built list of names to look for. It was set up that way since the mapping team was repeating the same process over and over, so they just use a script to resource an existing mxd and save it as a new one. If I can figure out why the simple arcpy.Exists() is failing, then I should be able to adjust the other parts.
Does that make sense at all? I don't know how to tell if the mxd itself is corrupt is some manner, or if there is something I am completely missing.