Just to clarify, it sounds like you're renaming the images outside of Photo Mechanic. If you rename them with Photo Mechanic (In this case: "NOLA-{filenamebase}"), the images won't go missing.
Similarly, if you use Photo Mechanic to move your images to those subfolders, its going to update their locations in the catalog.